DFS & BFS 예제

DFS & BFS 예제

1. 얼음 문제

N X M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.

n, m = map(int, input().split()) graph = [list(map(int, input())) for _ in range(n)] def dfs(x, y): # 범위에 벗어나느 경우 False if x < 0 or x >= n or y < 0 or y >= m: return False if graph[x][y] == 0: graph[x][y] = 1 dfs(x+1, y) dfs(x-1, y) dfs(x, y+1) dfs(x, y-1) return True # 방문한 노드일 경우 False return False result = 0 for i in range(n): for j in range(m): if dfs(i,j) == True: result += 1 print(result)

풀이

1. 현재 노드가 주어진 범위를 벗어나는 경우 종료 (return False)

2. 현재 노드를 방문 처리하지 않았다면 방문 처리하기

3. 현재 노드의 상, 하, 좌, 우 모두 재귀적으로 호출 후 True 반환 (return True)

4. 현재 노드가 방문되어 있다면 종료 (return False)

2. 미로게임

동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혔다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.

동빈이의 위치는 (1,1)이며 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다.

이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

from collections import deque n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) # 방향 벡터 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): queue = deque() queue.append([x, y]) while queue: # 값 초기화 x, y = queue.popleft() # 4가지 방향 for i in range(4): nx = x + dx[i] ny = y + dy[i] # 범위 벗어난 경우 무시 if nx < 0 or ny < 0 or nx >= n or ny >= m: continue # 막힌 경우 무시 if graph[nx][ny] == 0: continue # 전 위치에서 +1 if graph[nx][ny] == 1: queue.append([nx,ny]) graph[nx][ny] = graph[x][y] + 1 bfs(0,0) print(graph[n-1][m-1])

풀이

1. 초기 큐에 x,y를 넣음

2. 큐에서 x,y를 뽑고 4방향으로 확인

3. 주어진 영역을 벗어난 경우 무시

4. 0(이동할 수 없는 칸)인 경우 무시

5. 해당 위치를 처음 방문한다면 전 위치에서 +1하고 큐에 넣음

6. 가장 오른쪽 아래까지의 최단 거리 반환

7. (0,0)에서부터의 bfs 출력

from http://doyyy.tistory.com/144 by ccl(A) rewrite - 2021-08-22 18:26:48