from copy import deepcopy from collections import deque # 섬 개수 타운팅 def bfs(x, y): global visited visited[x][y] = True q = deque([(x, y)]) while q: x, y = q.popleft() chk = False for i in range(4): nx = x+dx[i]; ny = y+dy[i] if 0

어제도 BFS 문제를 풀면서 아래 첫번째 코드 처럼 q에 [현재 층수, 움직인 횟수] 형태로 append하였더니 시간초과가 나왔다. deque로 BFS 문제를 풀때는 방문 여부를 처리하는 부분이 별개로 필요하다는 것을 다시 한번 깨닫게 하였다. F, S, G, U, D = map(int, input().split()) from collections import deque q = deque([(S, 0)]) tmp = [] if U > 0: tmp.append(U) if D > 0: tmp.append(-1 * D) chk = False while q: floor, cnt = q.popleft() if floor == G: chk = True break for a in tmp: f = floor + a i..

#높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램 from collections import deque def bfs(x, y): global h, area, areaGraph, visited dx = [0, 1, 0, -1]; dy = [1, 0, -1, 0] q = deque([(x, y)]) visited[x][y] = True areaGraph[x][y] = True chk = False while q: x, y = q.popleft() for i in range(4): nx = x + dx[i]; ny = y + dy[i] if 0

DFS 와 BFS로 풀이해보았다. DFS def dfs(p, cnt): global chk if p == c: chk = True print(cnt) return for i in range(101): if graph[p][i] == 1 and visited[i] == False: visited[i] = True dfs(i, cnt + 1) visited[i] = False n = int(input()) p, c = map(int, input().split()) m = int(input()) graph = [[0]*(101) for _ in range(101)] for i in range(m): x, y = map(int, input().split()) graph[x][y] = 1 graph[y][x] =..

쉬운줄 알았던데 생각보다 마음대로 풀리지 않아서 상당히 애먹었던 문제이다. 처음에는 아래와 같이 풀이를 했으나 무한루프에 빠지는 현상을 발견했다. 왜그런건지 궁금한데... 일단 추정상 not in 으로 리스트안에 값을 찾는 로직이 인덱싱하는 것보다 시간복잡도가 더 커서 그런것이라고 생각이 든다. # 수빈의 현재 점 = N, 동생의 점 = K # 위치가 X일때 걷는다면 1초 후에 X-1, X+1로 이동 # 순간이동인 경우에는 1초 후에 2*X로 이동 from collections import deque N, K = map(int, input().split()) time = 0 q = deque([(N, time)]) visited = [N] while q: x, t = q.popleft() if x == ..

Queue 를 이용한 BFS로 풀이한 문제이다. from collections import deque N = int(input()) graph = []; visited = [] for _ in range(N): tmp = list(map(int, input())) graph.append(tmp) visited.append(list(map(lambda x : x == 1, tmp))) result = [] dx = [1, 0, -1, 0]; dy = [0, 1, 0, -1] for i in range(N): for j in range(N): if graph[i][j] == 1 and visited[i][j] == True: q = deque([(i, j)]) num = 1 visited[i][j] = Fa..