너비 우선 탐색(BFS, Breadth-First Search)
요약
BFS를 구현할 때 핵심은 큐를 이용하여 다음 노드를 순차적으로 순회하는게 핵심.
문제 - 탈출
풀이 시간: 1시간 반
문제 요약: 2차원 배열 맵안에서 사악한 암흑군주 이민혁으로부터 고슴도치를 탈출 시키는 문제.
접근방법
고슴도치는 상하좌우로 '.'위치만 이동 가능한 것을 - BFS로 구현
홍수 또한 상하좌우로 '.'위치만 이동 가능한 것을 -BFS로 구현
각 턴마다 홍수 BFS, 고슴도치 BFS 돌려야 함.
홍수가 일어날 자리에 고슴도치가 가면 안되기 때문에 홍수BFS가 먼저 되어야 함.
과정을 표로 그려보자!
입력값:
3 6
D...*.
.X.X..
....S.
이런 느낌으로 진행이 될 것이다.
문제 구현에서 힘들었던 점
해당 문제는 2차원 백터를 다루는데 능숙하다면 크게 어렵지 않게 구현이 가능 했다.
다만 위 이미지와 같은 과정을 큐에서 하나씩 빼면서 반복해야 하기에,
홍수 범람하는 반복문과 큐와, 고슴도치 이동을 반복문과 큐로 따로따로 구현 해야한다는 발상이 생각보다 금방 떠오르지는 않았다.
코드
import sys
from collections import deque
#sys.stdin.read()
sys.stdin = open('input.txt', 'r')
map_y, map_x = map(int,sys.stdin.readline().split())
#지도 크기를 받는 코드
#print(map_x,map_y)
map1= []
for _ in range(map_y):
map1.append(list(sys.stdin.readline().rstrip()))
#지도 정보 받는 코드
#print(map1)
sonic = (0,0) #고슴도치 좌표 변수 초기화
dst = (0,0) #동굴 좌표 변수 초기화
stone = (0,0) #돌 좌표 변수 초기화
fluid = deque() #홍수 초기 좌표 변수 초기화 - 복수개일 수 있기 때문에 리스트나, deque같은 이터너블 타입으로 받아야함.
#초기 위치 지정
for y in range(map_y): #반복문을 돌며 MAP에 동굴,돌,홍수,고슴도치 좌표 탐색.
for x in range(map_x):
if map1[y][x] == "D": # 목적지: 동굴 좌표 변수에 업뎃
dst= (y,x)
elif map1[y][x]== "*": # 홍수 좌표 변수에 업뎃
fluid.append((y,x))
elif map1[y][x]== "S": # 출발지: 고슴도치 좌표 변수에 업뎃
sonic =(y,x)
direction = [(-1,0),(1,0),(0,-1),(0,1)] 리스트(튜플) 구성으로 상하좌우 이동용 방향세트 변수 정의
sonic_bfs = deque() #고슴도치 모든 이동경로를 BFS탐색할 것이기에 데크로 구현
sonic_bfs.append((sonic[0],sonic[1],0)) # 고슴도치-큐에 초기값 append
fluid_bfs = deque() #홍수큐 초기화
for fy, fx in fluid:
fluid_bfs.append((fy, fx)) #홍수는 복수개 일 수 있어서 반복문으로 큐에 삽임
time = 0
while True:
#D의 좌표를 선입력 받기 때문에 이전 회차에서 고슴도치가 도달 시 value 변경을 감지
if map1[dst[0]][dst[1]] != 'D':
break
#분기마다 홍수-큐에 있는 만큼 위치를 반복하며 상하좌우 범람
for _ in range(len(fluid_bfs)):
fx,fy = fluid_bfs.popleft()
for dy,dx in direction:
if 0 <= fy+dy < map_x and 0 <= fx+dx < map_y:
if map1[(fx+dx)][(fy+dy)] == '.':
map1[(fx+dx)][(fy+dy)] = '*'
fluid_bfs.append((fx+dx,fy+dy))
#고슴도치가 진행 불가를 고슴도치-큐에 더이상 꺼낼게 없을 때로 판단
if not sonic_bfs:
print("KAKTUS")
break
#분기마다 고슴도치-큐에 있는 만큼 상하좌우를 비교하며 다음 진행.
#'.' 'D' 일때 탐지를 해서 값 변경,
#고슴도치 자체가 이동 횟수를 가진 value가 되어 회차정보를 가지고 있음.
for _ in range(len(sonic_bfs)):
cx,cy,cost = sonic_bfs.popleft()
for dy,dx in direction:
if 0 <= cy+dy < map_x and 0 <= cx+dx < map_y:
if map1[(cx+dx)][(cy+dy)] == ('.'):
map1[(cx+dx)][(cy+dy)] = cost+1
sonic_bfs.append((cx+dx,cy+dy,cost+1))
elif map1[(cx+dx)][(cy+dy)] == ('D'):
print(cost+1)
map1[(cx+dx)][(cy+dy)] = cost+1
일단함