문제
- https://www.acmicpc.net/problem/3055
- 너비 우선 탐색 진행 과정을 타임라인 순서대로 관리하기
기록 포인트
- BFS가 시간순으로 진행된다는 점 이해하기
- BFS가 타임라인을 관리하기에 유용하다는 것이 잘 드러나는 문제였음
- 1차 답안에서는 홍수 진행 과정을 기록한 맵(매트릭스)과 고슴도치 이동 과정을 기록한 맵(매트릭스)를 분리해서 관리했음
- 하지만 1번 회차에서 홍수 이동 후 고슴도치 이동, 2번 회차에서 홍수 이동 후 고슴도치 이동, 이렇게 반복하며 맵을 업데이트하면 하나의 맵에서도 정보 관리가 가능함
- 답안 설계 전 발생 가능한 모든 경우의 수를 충분히 고려하기
- 1차 답안에서 오류가 발생했지만 반례를 찾지 못해 고생했음
- 결국 반례는, 맵 위에 홍수가 없을 때였음
- 처음 설계할 때 놓치면 나중에는 발견하기 어렵고, 또 발견하더라도 코드에 반영하기 난해할 수 있음
- 답안을 설계하기 전에 발생 가능한 경우의 수를 충분히 고려하는 습관을 들이자!
접근 방식
- 최종 답안
- 하나의 매트릭스에서 홍수 진행과정과 고슴도치 이동경로 정보를 관리
- BFS는 타임라인 관리가 가능하기 때문에 하나의 매트릭스에서 정보를 관리하는 편이 더 효율적임
- frontier는 "타임라인의 한 회차에서 진행해야 하는 항목(v)"들로 정의
- 처음 생성 시 홍수의 시작점들을 먼저 넣은 뒤 고슴도치의 출발점을 넣음
- frontier는 선입선출 방식으로 진행되므로 큐에는 아래의 순서로 정보가 담겨 처리됨
- (frontier의 맨 앞에서 항목을 뽑아 처리하고, 발견된 새로운 항목들은 frontier의 맨 뒤에 추가할 경우)
- 1번 회차에서 처리할 홍수 위치들 > 1번 회차에서 처리할 고슴도치 위치들 > 2번 회차에서 처리할 홍수 위치들 > 2번 회차에서 처리할 고슴도치 위치들 ...
- 타임라인별 frontier를 명시적으로 구분하기 위해 next_frontier 활용
- N번 시간에 frontier에 있는 항목(v1)을 처리하며 추가된 항목(v2)들을 next_frontier에 저장
- frontier에 있는 항목 모두 처리 이후 next_frontier로 frontier를 대체
- 다시 N+1번 시간에 frontier에 있는 항목들 처리
- 결과적으로 아래와 같이 단계를 나누어 처리 및 확인이 가능해짐
- 1번 회차: 홍수들 진행과정 처리, 그 다음 고슴도치 이동경로 처리
- 2번 회차: 홍수들 진행과정 처리, 그 다음 고슴도치 이동경로 처리
- 목적지에 도착하거나 새로 처리할 항목이 없을 때까지 진행
- 하나의 매트릭스에서 홍수 진행과정과 고슴도치 이동경로 정보를 관리
- 1차 답안
- 홍수 진행과정 매트릭스와 고슴도치 이동경로 매트릭스를 분리
- BFS로 홍수 매트릭스의 각 좌표에 홍수가 어느 시점에 진입하는지 기록
- 즉, 홍수가 각 좌표에 도착하기 위한 최단 거리(최단 시간) 기록
- 이 때, 목적지와 장애물은 이동 불가 처리
- BFS로 경로 매트릭스의 각 좌표에 고슴도치가 어느 시접에 진입하는지 기록
- 즉, 고슴도치가 각 좌표에 도착하기 위한 최단 거리(최단 시간) 기록
- 이 때, 장애물은 이동 불가 처리
- 또한, 홍수 매트릭스의 동일 좌표 값을 확인하여 해당 좌표에 홍수가 더 빠르거나 동일한 시점에 도착했으면 이동 불가 처리
- 특정 좌표에 '홍수의 도착 시간' <= '고슴도치의 도착 시간'이면 이동 불가
- 탐색을 마친 후, 목표 좌표에 고슴도치가 도착했는지 확인
제출 답안
최종 답안
import sys
R, C = tuple(map(int, sys.stdin.readline().split()))
matrix = []
START, GOAL = None, None
WIZARD = []
for r in range(R):
row = [v for v in sys.stdin.readline().rstrip()]
for c, value in enumerate(row):
if value == "D":
GOAL = (r, c)
elif value == "S":
START = (r, c)
elif value == "*":
WIZARD.append((r, c))
matrix.append(row)
# 2단계: 각 매트릭스의 탐색 실시
dxs = [-1, 1, 0, 0]
dys = [0, 0, -1, 1]
# frontier 큐 생성:
# - 행위자 정보를 함께 저장
# - 홍수 먼저, 고슴도치 다음
frontier = [(v, "*") for v in WIZARD] + [(START, "S")]
time = 0
success = False
# print("[time]", time)
# print(" matrix:")
# for row in matrix:
# print(" ", row)
# print(" frontier:")
# print(" ", frontier)
while not success and frontier:
time += 1
next_frontier = []
for v1, actor in frontier:
x1, y1 = v1
for dx, dy in zip(dxs, dys):
x2, y2 = x1+dx, y1+dy
v2 = (x2, y2)
# 존재하는 위치인지 확인
if x2 < 0 or x2 >= R or y2 < 0 or y2 >= C:
continue
# 장애물이 놓인 위치인지 확인
status = matrix[x2][y2]
if status == "X":
continue
# actor에 따라 구분하여 행동
# 행위자가 홍수인 경우, 이동하려는 위치의 상태가 홍수, D이면 제외
if actor == "*" and (status in [".", "S"]):
matrix[x2][y2] = "*"
next_frontier.append((v2, "*"))
# 행위자가 고슴도치인 경우, 아동하려는 위치의 상태가 홍수, 본인이면 제외
elif actor == "S" and status == "D":
# 도착지에 도착했으면 탐색 종료
matrix[x2][y2] = "S"
success = True
break
elif actor == "S" and status == ".":
matrix[x2][y2] = "S"
next_frontier.append((v2, "S"))
frontier = next_frontier
# print("[time]", time)
# print(" matrix:")
# for row in matrix:
# print(" ", row)
# print(" frontier:")
# print(" ", frontier)
if success:
print(time)
else:
print("KAKTUS")1차 답안
import sys
from collections import deque
R, C = tuple(map(int, sys.stdin.readline().split()))
matrix = []
START, GOAL = None, None
BLOCK, WIZARD = [], []
for r in range(R):
row = [v for v in sys.stdin.readline().rstrip()]
for c, value in enumerate(row):
if value == "D":
GOAL = (r, c)
elif value == "S":
START = (r, c)
elif value == "*":
WIZARD.append((r, c))
elif value == "X":
BLOCK.append((r, c))
matrix.append(row)
# 1단계: 매트릭스 생성
# 홍수 매트릭스 생성
flood_matrix = []
for r in range(R):
row = [0]*C
flood_matrix.append(row)
# 홍수 매트릭스에 발원지, 목적 지점, 장애물 표시
flood_matrix[GOAL[0]][GOAL[1]] = float("inf")
for r, c in WIZARD:
flood_matrix[r][c] = 1
for r, c in BLOCK:
flood_matrix[r][c] = -1
# 이동경로 매트릭스 생성
route_matrix = []
for r in range(R):
row = [0]*C
route_matrix.append(row)
# 이동경로 매트릭스에 출발 지점, 장애물 표시
route_matrix[START[0]][START[1]] = 1
for r, c in BLOCK:
route_matrix[r][c] = -1
# 2단계: 각 매트릭스의 탐색 실시
dxs = [-1, 1, 0, 0]
dys = [0, 0, -1, 1]
frontier = deque(WIZARD[:])
while frontier:
v1 = frontier.popleft()
x1, y1 = v1
for dx, dy in zip(dxs, dys):
x2, y2 = x1+dx, y1+dy
# 존재하는 위치인지 확인
if x2 < 0 or x2 >= R or y2 < 0 or y2 >= C:
continue
# 장애물이거나 이미 탐색된 영역인지 확인
# (홍수 매트릭스의 경우, 도착지점 여부 함께 확인)
if flood_matrix[x2][y2] != 0:
continue
# 탐색되지 않은 영역인 경우
flood_matrix[x2][y2] = flood_matrix[x1][y1] + 1
frontier.append((x2,y2))
frontier = deque([START])
while frontier:
v1 = frontier.popleft()
x1, y1 = v1
time1 = route_matrix[x1][y1]
for dx, dy in zip(dxs, dys):
x2, y2 = x1+dx, y1+dy
time2 = time1 + 1
# 존재하는 위치인지 확인
if x2 < 0 or x2 >= R or y2 < 0 or y2 >= C:
continue
# 장애물이거나 이미 탐색된 영역인지 확인
if route_matrix[x2][y2] != 0:
continue
# 이미 물이 차오른 영역인지 확인
# [주의!] 맵에 WIZARD가 하나도 없었던 경우,
# - 홍수 매트릭스의 값들은 모두 초기값 그대로 0으로 남아 있음
# - 이 경우는 고슴도치가 이동 가능한 상황이므로 분리해주어야 함
if flood_matrix[x2][y2] != 0 and flood_matrix[x2][y2] <= time2:
continue
# 이동 가능한 영역인 경우
route_matrix[x2][y2] = time2
frontier.append((x2,y2))
# 3단계: 좌표 확인하기
x, y = GOAL
time = route_matrix[x][y]
if time:
print(time - 1)
else:
print("KAKTUS")
개발자 서자헌