이 문제는 너비우선탐색(Breadth-first search)을 기초로 하되, 세차장의 위치를 탐색하는 코드와 소나기의 위치를 판단한 후 매 시간마다 소나기를 확산시키는 코드를 작성하면 이 문제를 쉽게 풀 수 있다. 따라서 이를 위해 작성해야할 코드를 요약하자면,
(준비과정) 데이터 받고 정리하는 코드
태범이가 너비우선탐색을 통해 이동하는 알고리즘 코드
세차장 위치를 탐색하는 코드
소나기의 위치를 판단한 후 매분마다 소나기를 확산시키는 코드
위의 3가지 코드이다. 이제 하나하나 어떻게 작성하는지 알아보도록 하겠다.
1. (준비과정) 입력값을 받고 변수에 저장하는 코드 + 이외에 필요한 변수를 준비
import sys
from collections import deque
# R행 C열 받는다.
R, C = map(int, sys.stdin.readline().split())
# R행의 환경 하나하나 env에 담는다.
env = []
for _ in range(R):
env.append(list(input()))
# 태범이가 방문한 위치 기록하기 위한 리스트.
visited = [[0 for _ in range(C)] for _ in range(R)]
우선 입력값을 받고 변수에 저장하는 코드와, 그 이외에 필요한 변수들을 위와 같이 준비한다. 여기서 visited 변수는 태범이의 방문을 체크하기 위한 코드로 너비우선탐색 코드를 작성하는데 쓸 변수이다.
2. 태범이가 너비우선탐색을 통해 이동하는 알고리즘 코드
가장 먼저 태범이의 움직임의 경로를 시뮬레이션 하기 위해 너비우선탐색 코드를 실현시킬 필요가 있다.
# 이동 관련 리스트
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
# 너비 우선 탐색
def bfs(start_x, start_y):
# 큐를 통해 자료구조 힙을 준비해준다.
queue = deque()
# 처음 태범이의 위치 기입 (세차장 위치)
queue.append([start_x, start_y, 0])
# 그 위치를 방문했다고 표시.
visited[start_y][start_x] = 1
# 시간 변화를 구현하기 위한 임시 변수
tmp = 0
# **비를 처음에 내려주지 않으면 오답 나타남.
# 즉 비가 먼저 내리고 이동을 한다는 가정인 듯 하다.
spread_rainy()
# 큐 안에 값이 다 없어질 때까지 반복
while queue:
x, y, dist = queue.popleft()
# 이동한 시간이 달라질 경우 비를 확산한다.
if (tmp != dist):
tmp =dist
visited_rain = [[0 for _ in range(C)] for _ in range(R)]
spread_rainy()
for i in range(len(dx)):
next_x = x + dx[i]
next_y = y + dy[i]
# 무효한 위치로의 이동 무효화
if not ((0<=next_x < C) and (0 <= next_y < R)):
continue
# 방문했던 위치에 대한 이동 무효화
if (visited[next_y][next_x] == 1):
continue
# 해당 위치에 뭐가 있는지 확인 후 집일 경우 바로 거리 출력
# 빈칸일 경우 이동 후 방문처리 한 후에 큐에 위치 기입
# 그 외 소나기, 강일 경우 아무것도 안하고 다음 루프로 바로 이동
if (env[next_y][next_x] == "H") :
return (dist + 1)
elif (env[next_y][next_x] == "."):
visited[next_y][next_x] = 1
queue.append([next_x, next_y, dist + 1])
else:
continue
return "FAIL"
해당 코드는 위를 통해 실현시킬 수 있는데, 이 코드의 핵심만 요약해서 설명을 하자면,
움직임을 위한 변수를 준비한다. (dx, dy)
너비우선탐색을 위한 힙 자료구조인 큐를 준비한다. (queue = deque())
처음 위치와 현재까지 누적 이동시간(거리)을 큐에 넣어준 후 해당 위치를 방문표시 한다. (queue.append(start_x, start_y, dist)
비를 확산시킨다. (spread_rainy()) → 이 부분은 비 구현 코드에서 더욱 상세히 설명하겠다.
이동한 후 해당 위치가 유효하다면 이동을 한 후, 이동하고 난 후의 위치와 누적 이동시간(거리)를 큐에 다시 담아준다. (queue.append([next_x, next_y, dist+1]))
만약 이동한 위치가 집("H")일 경우 바로 코드를 끝내고 누적 이동시간을 출력한다. (return (dist+1))
만약 누적 이동시간이 달라졌다면 시간이 지나갔다는 의미이므로 비를 확산시킨다. (if (tmp != dist) ... 해당 코드)
위와 같다. 결국은 너비우선탐색을 하나하나 진행하면서 누적된 이동시간(거리)를 큐에 담아 계속 시뮬레이션을 진행하는 코드이며, 단지 일반적인 너비우선탐색과의 차이점은 매 일분이 지날때마다 비를 확산시킨다는 점이다. 이 문제에서 비와 태범이의 이동에 대한 순서가 구체적으로 주어지지 않았는데, 비를 먼저 확산하고 나서 태범이가 이동할 경우에 오답이 나질 않게 된다.
그렇기 때문에 너비우선탐색을 시작하기 전에 소나기를 한번 확산시켜주고 나서, 시간이 지남을 판단하기 위한 코드(tmp 와 관련된 코드들)를 통해 시간변화를 확인하고 시간변화가 탐지될 때마다 다시 또 소나기를 확산시켜주어야만 한다. 그렇게 소나기의 확산 함수가 담긴 너비우선탐색 코드를 완성했다. (소나기 확산 함수는 아래에서 더 구체적으로 알아볼 것이다.)
3. 세차장 위치를 탐색하는 코드
2번 너비우선탐색을 진행하기 위해서는 가장 먼저 "start_x"와 "start_y", 즉 태범이의 처음 위치를 알아야만 한다. 문제에서 태범이는 "세차장에서 세차를 하고 집으로 돌아가려고 한다" 라는 조건이 주어졌기에 시작점은 세차장의 위치, 즉 환경(env)안에서 "W"가 존재하는 위치가 된다.
def find_w(env):
for y in range(len(env)):
for x in range(len(env[0])):
if (env[y][x] == "W"):
return (x, y)
이는 위 코드와 같이 env 환경이 주어졌을 때, 모든 행과 열에 대해 "W"의 위치를 판단한 후 그 위치를 출력해주도록 하면 된다. 그리고 이 위치값은 너비우선탐색의 start_x, start_y 값으로 주어질 예정이다.
4. 소나기의 위치를 판단한 후 매분마다 소나기를 확산시키는 코드
소나기 확산과 함께하는 너비우선탐색 코드, 그리고 태범이의 초기 위치를 알려주는 코드를 모두 작성했으니, 마지막으로 소나기를 확산해주는 코드를 작성해주면 된다.
def spread_rainy():
# (**중요**)일분마다 비를 확산하기 위해 보조적으로 사용하는 리스트.
visited_rain = [[0 for _ in range(C)] for _ in range(R)]
for y in range(len(env)):
for x in range(len(env[0])):
# 해당 위치가 비이고, 한번도 확산되지 않은 비일 경우
if (env[y][x] == "*") and ((visited_rain[y][x] == 0)):
# 확산 됬다고 표시하고,
visited_rain[y][x] = 1
# 각각의 이동위치를 얻어낸 후 (상하좌우)
for i in range(len(dx)):
next_x = x + dx[i]
next_y = y + dy[i]
# 무효한 위치 제거
if not ((0<=next_x < C) and (0 <= next_y < R)):
continue
# 확산된 비의 경우는 확산하지 않도록 하고.
if (visited_rain[next_y][next_x] == 1):
continue
# 확산되는 위치에 아무것도 없을 때
if (env[next_y][next_x] == "."):
# 비를 더한다.
env[next_y][next_x] = "*"
visited_rain[next_y][next_x] = 1
이 코드는 위와 같이 표현할 수 있다. 즉, 모든 환경에 대해서 확산을 아직 진행하지 않은 소나기("*")가 어딨는지 확인하고, 소나기 확산에 대한 여부를 체크해준 후, 상하좌우(dx, dy)로 유효한 위치(0<=next_x<C, 0<=next_y<R)이며, 아무것도 없는 위치(".")에만 소나기를 확산시켜준 후 그 확산된 소나기에도 소나기 확산 여부를 체크해주면 된다.
여기서 확산시킨 소나기와 확산된 소나기 모두에 소나기 확산 여부(visited_rain)을 체크해주는데, 이는 딱 한번의 일분이라는 시간동안 확산이 될 소나기인가 확산이 되지 않을 소나기인가를 기록해주기 위한 것이다.
만약 이를 체크해주지 않게 되면 소나기 확산 코드를 한번 진행할 때 이미 확산된 소나기가 또 확산되고 또 확산되는 결과를 만들어서 1분 밖에 지나지 않았는데 모든 공간이 소나기로 뒤덮이는 오류가 발생한다.
아무튼 이렇게 소나기 확산 코드까지 작성해주었고, 1~4번 코드를 하나로 묶으면 문제없이 이 문제를 풀 수 있게 된다.
코드
import sys
from collections import deque
# R행 C열 받는다.
R, C = map(int, sys.stdin.readline().split())
# R행의 환경 하나하나 env에 담는다.
env = []
for _ in range(R):
env.append(list(input()))
# 태범이가 방문한 위치 기록하기 위한 리스트.
visited = [[0 for _ in range(C)] for _ in range(R)]
# 일분마다 비를 확산하기 위해 보조적으로 사용하는 리스트.
visited_rain = [[0 for _ in range(C)] for _ in range(R)]
# 이동 관련 리스트
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
# 너비 우선 탐색
def bfs(start_x, start_y):
# 큐를 통해 자료구조 힙을 준비해준다.
queue = deque()
# 처음 태범이의 위치 기입 (세차장 위치)
queue.append([start_x, start_y, 0])
# 그 위치를 방문했다고 표시.
visited[start_y][start_x] = 1
# 시간 변화를 구현하기 위한 임시 변수
tmp = 0
# **비를 처음에 내려주지 않으면 오답 나타남.
# 즉 비가 먼저 내리고 이동을 한다는 가정인 듯 하다.
spread_rainy()
# 큐 안에 값이 다 없어질 때까지 반복
while queue:
x, y, dist = queue.popleft()
# 이동한 시간이 달라질 경우 비를 확산한다.
if (tmp != dist):
tmp =dist
visited_rain = [[0 for _ in range(C)] for _ in range(R)]
spread_rainy()
for i in range(len(dx)):
next_x = x + dx[i]
next_y = y + dy[i]
# 무효한 위치로의 이동 무효화
if not ((0<=next_x < C) and (0 <= next_y < R)):
continue
# 방문했던 위치에 대한 이동 무효화
if (visited[next_y][next_x] == 1):
continue
# 해당 위치에 뭐가 있는지 확인 후 집일 경우 바로 거리 출력
# 빈칸일 경우 이동 후 방문처리 한 후에 큐에 위치 기입
# 그 외 소나기, 강일 경우 아무것도 안하고 다음 루프로 바로 이동
if (env[next_y][next_x] == "H") :
return (dist + 1)
elif (env[next_y][next_x] == "."):
visited[next_y][next_x] = 1
queue.append([next_x, next_y, dist + 1])
else:
continue
return "FAIL"
def find_w(env):
for y in range(len(env)):
for x in range(len(env[0])):
if (env[y][x] == "W"):
return (x, y)
def spread_rainy():
# **초기화를 여기다 안해주면 초기화가 안됨.
visited_rain = [[0 for _ in range(C)] for _ in range(R)]
for y in range(len(env)):
for x in range(len(env[0])):
# 해당 위치가 비이고, 한번도 확산되지 않은 비일 경우
if (env[y][x] == "*") and ((visited_rain[y][x] == 0)):
# 확산 됬다고 표시하고,
visited_rain[y][x] = 1
# 각각의 이동위치를 얻어낸 후 (상하좌우)
for i in range(len(dx)):
next_x = x + dx[i]
next_y = y + dy[i]
# 무효한 위치 제거
if not ((0<=next_x < C) and (0 <= next_y < R)):
continue
# 확산된 비의 경우는 확산하지 않도록 하고.
if (visited_rain[next_y][next_x] == 1):
continue
# 확산되는 위치에 아무것도 없을 때
if (env[next_y][next_x] == "."):
# 비를 더한다.
env[next_y][next_x] = "*"
visited_rain[next_y][next_x] = 1
# 세차장 위치 수색 (시작점)
index_x, index_y = find_w(env)
# 결과 출력
print(bfs(index_x, index_y))
