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 출력