(Python) bfs(너비 우선 탐색) 백준 2178, 7576, 14502

---

bfs(너비 우선 탐색)

트리 구조나 그래프 구조에서 방문 탐색법이다.

큐를 사용하여

1. 시작점을 큐에 저장함

2. 시작점에 연결되어 있는 모든 자식 노드를 저장하고 차례로 방문 후 방문 처리

3. 2번 방법을 반복

4. 방문 가능 노드를 모두 방문했다면 탐색 끝

---

2178번 미로탐색

https://www.acmicpc.net/problem/2178

그래프 구조 중 기초 문제

 

N X M 구조 그래프

갈 수 있는 칸을 1, 갈 수 없는 칸을 0으로 주어지고 상하좌우로 이동하여 최소칸을 거치는 경우의 수 찾기

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

시작점 (1, 1)에서 도착점인 (N, M)으로 이동

 

1. 시작점 1,1 을 큐에 넣음

2. 상하좌우 중 갈 수 있는 칸인 1의 값을 큐에 넣어줌

3. (N, M) 좌표에 도착했으면 반복문 종료

 

입력 코드

from collections import deque # bfs를 사용하기 위해 큐 자료형 사용
def bfs(x, y):
	함수 작성
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]

print(bfs(0, 0)) # 좌표는 0부터 시작하기 때문에 함수 호출를 (0, 0)으로

bfs 함수 코드

def bfs(x, y): # 매개변수로 좌표값 받기
  queue = deque() # 큐를 변수에 넣어 편하게 사용
  queue.append((x, y)) # 좌표를 큐에 넣기
  while queue:
    x, y = queue.popleft() # 좌표를 빼기
    for i in range(4): # 상하좌우 확인
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue
      if graph[nx][ny] == 0:
        continue
      if graph[nx][ny] == 1: # 이동할 수 있는 칸 1인 경우
        graph[nx][ny] = graph[x][y] + 1 # 이동 칸 횟수를 알기 위해 그전 칸에 횟수 저장
        queue.append((nx, ny)) # 이동할 수 있는 칸을 큐에 저장 후 반복
  return graph[n - 1][m - 1] # 0,0에서 시작했기에 끝은 n-1, m-1로

 

칸 이동횟수는 시작점 포함 횟수이고

시작점이 1로 되어있기 때문에 이동할 수 있는 상하좌우를 모두 + 1 해주어 저장해 주면

끝 점 값이 횟수가 된다.

---

7576번 토마토

https://www.acmicpc.net/problem/7576

그래프 응용문제

M X N 상자

익은 토마토 1, 익지 않은 토마토 0, 빈 곳 -1 

익은 토마토와 붙어 있는 토마토는 하루가 지나면 익는다.

모든 토마토가 익는 최소 일수를 구하라

 

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

2178번은 시작점이 하나였지만 7576 토마토 문제는 시작점이 여러 개가 되는 문제이다.

시작점이 여러 개면 미리 토마토 위치를 다 넣어두면 된다.

 

1. 입력받은 토마토들 중 익은 토마토인 1의 위치를 큐에 저장해 둔다.

2. 상하좌우가 0인 경우만 1로 바꾸어 준다.

3. 안 되는 경우는 -1로 출력하고, 모든 칸을 돌고 결과를 출력한다.

 

입력 코드

import sys # 입력이 많을 경우에는 사용
from collections import deque # 큐

m, n = map(int, input().split()) #가로 m, 세로 n
queue = deque() # 미리 큐 설정
graph = []
for i in range(n):
  graph.append(list(map(int, sys.stdin.readline().split())))

dx = [1, -1 , 0, 0]
dy = [0, 0, -1, 1]

result = 0 # 결과값 저장할 변수
for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      queue.append((i, j)) # 익은 토마토의 위치를 차례로 큐에 넣기

bfs 코드 따로 함수로 만들지 않아도 됨 (재귀를 하지 않음)

def bfs(): # 미리 토마토 위치 저장 후 bfs
  while queue:
    x, y = queue.popleft() # 큐에서 하나 꺼내기
    for i in range(4): # 상하좌우
      nx = x + dx[i]
      ny = y + dy[i]
      if nx >= 0 and nx < n and ny >= 0 and ny < m and graph[nx][ny] == 0:
        graph[nx][ny] = graph[x][y] + 1 # 위 문제와 똑같이 일수 저장
        queue.append((nx, ny)) # 익은 토마토로 변경된 위치를 큐에 다시 넣기
  return graph

위 문제와 달리 첫 번째 익은 토마토의 일수는 빼고 계산하기에 결과 값에 -1을 해주면 됨

 

전체 코드

import sys
from collections import deque
def bfs(): # 미리 토마토 위치 저장 후 bfs
  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx >= 0 and nx < n and ny >= 0 and ny < m and graph[nx][ny] == 0:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx, ny))
  return graph
m, n = map(int, input().split())
queue = deque()
graph = []
for i in range(n):
  graph.append(list(map(int, sys.stdin.readline().split())))

dx = [1, -1 , 0, 0]
dy = [0, 0, -1, 1]
result = 0
for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      queue.append((i, j))
bfs() # 함수 호출해주어 계산
for i in graph:
  for j in i:
    if j == 0: # 0이 존재하면 모든 토마토가 익지 않은 경우
      print(-1)
      exit(0)
  result = max(result, max(i)) # 이중리스트 최대값 구하기(정답)
print(result - 1)

---

14502번 연구소

https://www.acmicpc.net/problem/14502

7576번 토마토 문제에서 빈칸을 넣어주는 응용 버전

 

N X M 연구소에 바이러스가 퍼진다.

0은 빈칸, 1은 벽, 2는 바이러스가 있는 위치이다. 

여기서 벽을 3개를 세워서 안전지대를 최대로 만들어내는 문제이다.

토마토 문제에서 내가 빈칸을 3개 만들어서 최대한 익은 토마토가 퍼지지 않게 하면 된다.

 

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈칸의 개수는 3개 이상이다.

 

문제 풀이가 비슷하나 벽 3개를 넣는 모든 경우의 수를 따져 가장 바이러스가 적게 퍼진 경우를 

찾으면 된다.

한 번 반복할 때 리스트를 복사해서 벽 넣는 경우에서 결과를 찾으면 된다.

from collections import deque
import copy # 그래프 리스트 깊은 복사를 위해

def wall(count): #벽을 3개를 추가하는 함수
  if count == 3: # 벽 3개를 다 넣으면 bfs를 해준다.
    bfs()
    return
  for i in range(n): 
    for j in range(m):
      if graph[i][j] == 0: # 차례대로 벽을 넣어준다. 
        graph[i][j] = 1
        wall(count + 1)
        graph[i][j] = 0 # 벽을 다넣고 bfs를 하고 다시 벽을 원상태로 해둔다.
          
def bfs():
  queue = deque()
  wall_graph = copy.deepcopy(graph) # 복사할 리스트를 만든다.
  for i in range(n):
    for j in range(m):
      if wall_graph[i][j] == 2:
        queue.append((i, j))
  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue
      if wall_graph[nx][ny] == 0:
          wall_graph[nx][ny] = 2
          queue.append((nx, ny))
  global result # 여기서 복사한 리스트의 결과값을 저장한다.
  num = 0
  for i in range(n):
    for j in range(m):
      if wall_graph[i][j] == 0:
        num += 1
  result = max(result, num) # 최대로 많은 안전지대를 만든 결과를 저장
        
# n 세로 m 가로
n, m = map(int, input().split())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
result = 0
wall(0) # 벽을 매개변수 0을 넣어준다.
print(result)

 리스트를 깊은 복사를 통해 만드는 이유는 한 번  bfs 코드를 돌리면 원본에서 코드가 바뀌기 때문에 

다시 bfs를 돌릴 때 원본을 원상복구를 계속해주어야 하기에

돌릴 때마다 복사본을 사용

 

대신 백준에서 제출할 때는 pypy3로 제출해야 시간초과를 해결할 수 있다.