본문 바로가기

분류 전체보기

(263)
[백준] 2573 : 빙산 python 아이디어를 떠올리는 건 어렵지 않았지만 코드를 써가면서 반복문이 이렇게 많이 나오는 게 맞나..싶었다. 처음 제출한 코드가 시간초과가 나와서 역시 너무 비효율적이었구나 했는데 다른 사람들의 풀이를 참고해봐도 시간초과가 나오더라. 해결방법은 pypy3로 제출하는 거였다. NxM 사이즈의 cnt 리스트를 하나 만들고 BFS 탐색을 하다가 인접한 칸 중에 0인 게 있으면 cnt 리스트의 해당 위치값을 1씩 증가시켜두고, 빙산의 높이를 한 번에 바꿔주는 게 핵심이다. 모든 빙산이 녹았다는 걸 판단하기 위한 방식에 대해 고민을 많이 했었다. total = 0 # graph는 NxM 사이즈의 리스트 for g in graph: total += sum(graph) if total==0: # 모든 빙산이 녹았으니 0을..
[백준] 5014 : 스타트링크 python [f+1][2] 크기의 visited라는 list를 생성하고 0번 열에 방문체크를, 1번 열에 버튼을 누른 횟수를 저장해서 풀었다. from collections import deque f,s,g,u,d = map(int,input().split()) visited=[[0 for j in range(2)]for i in range(f+1)] def bfs(s,g): queue = deque() queue.append(s) visited[s][0]=1 while queue: a = queue.popleft() # 목표 지점에 도달했으면 횟수를 출력하고 리턴 if a==g: print(visited[a][1]) return # 위에 아직 방문하지 않은 층이 있다면 이동 if a+u0 and visited[a..
[백준] 9205 : 맥주 마시면서 걸어가기 python 현 위치에서 바로 행사장까지 갈 수 있다면 happy를 출력하고, 그렇지 않으면 갈 수 있는 편의점이 있는지 찾아본다. 있다면 그 편의점에서 맥주를 충전하고 위 과정을 반복한다. 모든 편의점을 들렀는데도 행사장까지 갈 수 없다면 sad를 출력하면 된다. import sys from collections import deque input = sys.stdin.readline # 두 좌표 사이의 거리를 구하는 함수 def dist(ax,ay,bx,by): return abs(ax-bx)+abs(ay-by) def bfs(start,fest,conv): queue = deque() # 시작점을 큐에 넣음 queue.append((start[0],start[1])) # 편의점 방문체크를 위한 리스트 visite..
[백준] 14503 : 로봇 청소기 python 바라보는 방향을 유지한 채로 후진하는 것을 제대로 확인하지 못해서 계속 오답이 나왔다. 그렇게 어려운 문제는 아닌 것 같은데 왜 막상 풀면 잘 안 풀리는 건지..아직 연습이 많이 부족한 듯 from collections import deque import sys input = sys.stdin.readline dx = [-1,0,1,0] dy = [0,1,0,-1] n, m = map(int,input().split()) r,c,d = map(int,input().split()) graph = [] visited = [[False for j in range(m)]for i in range(n)] for i in range(n): graph.append(list(map(int,input().split())..
[백준] 2468 : 안전 영역 python 오타를 찾느라 고생을 좀 했다... import sys from collections import deque input = sys.stdin.readline n = int(input()) graph = [] for i in range(n): graph.append(list(map(int,input().split()))) # 최대 높이를 변수에 저장 max_height = max(map(max,graph)) dx = [-1,1,0,0] dy = [0,0,-1,1] def bfs(graph,visited,x,y,h): queue = deque() queue.append((x,y)) visited[x][y] = True while queue: a,b = queue.popleft() for i in range(..
[백준] 1525 : 퍼즐 python BFS를 쓰면 될 것 같다는 생각은 했지만 어떻게 풀어야 할지 감이 오질 않아서...결국 서치해보고 풀었다. 3x3표라고 해서 2차원 리스트를 고집하지 말고 문자열로 바꿔서 풀 것. 그리고 딕셔너리를 만들어서 변화하는 퍼즐의 상태와, 그 상태가 만들어지는 데까지 필요한 이동 횟수를 저장하는 것이 핵심이었다. from collections import deque target = "" for i in range(3): # 빈 칸을 지우고 이어붙이기 target += input().replace(' ','') # key: 각 퍼즐의 상태를 문자열로 만든 것 # value: 그 상태에 도달하는 데에 필요한 이동 횟수 visited = dict() # 초기상태가 되기 위한 이동횟수는 0 visited[target..
[백준] 10451 : 순열 사이클 python 1. T를 입력받는다. 2. 다음 과정을 T번 반복한다. 2-1. 정점의 개수 N을 입력받는다. 2-2. [n+1][] 크기의 리스트 graph를 생성한다. 2-3. data라는 리스트에 연결 정보를 저장한다. 2-4. 1부터 N+1까지 반복하면서 그래프에 연결 정보를 추가한다. 2-5. 방문 여부 확인을 위한 리스트 visited와 순열 사이클의 개수를 카운트 하기 위한 cnt를 초기화한다. 2-6. N개의 정점에 대해, 해당 정점을 아직 방문하지 않았다면 DFS를 수행하고 cnt를 1 증가시킨다. 2-7. cnt를 출력한다. 3. DFS 함수를 구현한다. import sys input = sys.stdin.readline t = int(input()) def dfs(v): visited[v] = Tr..
[백준] 11724 : 연결 요소의 개수 python 그래프에 연결 요소가 총 몇 개 있는지 카운트하는 문제다. 즉 그래프에서 모든 정점을 다 방문할 때까지 DFS나 BFS로 탐색한 횟수를 세면 된다. DFS를 사용해서 풀었는데 RecursionError가 발생해서 인위적으로 재귀횟수를 늘리는 코드를 추가했다. sys.setrecursionlimit(10**6) import sys input=sys.stdin.readline sys.setrecursionlimit(10**6) n,m=map(int,input().split()) cnt=0 visited = [False]*(n+1) graph=[[]for i in range(n+1)] for i in range(m): s,e = map(int,input().split()) graph[s].append(e) g..