[백준 3055번] : 탈출 파이썬 풀이
탈출
|
골드4
|
|
시간 제한
|
메모리 제한
|
제출
|
정답
|
맞힌 사람
|
정답 비율
|
|
1 초
|
128 MB
|
43061
|
14675
|
9961
|
32.101%
|
문제
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
입력
첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.
출력
첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.
예제 입력 1
|
3 3
D.*
...
.S.
|
예제 출력 1
|
3
|
예제 입력 2
|
3 3
D.*
...
..S
|
예제 출력 2
|
KAKTUS
|
예제 입력 3
|
3 6
D...*.
.X.X..
....S.
|
예제 출력 3
|
6
|
예제 입력 4
|
5 4
.D.*
....
..X.
S.*.
....
|
예제 출력 4
|
4
|
구현이 생각보다 까다로웠던 문제이다. 풀이방법 자체는 바로 생각했으나 미처 고려하지 못한 부분들때문에 오답판정을 여러번 받았다.
흑마법사 어쩌고 하는 문학적인 내용은 접어두고, 문제의 핵심을 간결하게 표현하면 다음과 같다.
고슴도치(S)는 홍수(*)를 피해 비버(D)로 이동
S와 *는 돌(X)를 통과할수 없고, 상하좌우 인접한 공간으로 이동함
고슴도치가 비버에게 도착하는데 걸리는 최소시간을 구하라
고슴도치는 물이 찰 예정인 공간으로 이동할수 없다. 즉 다음 시간에 물이 찰 예정인 공간으로 고슴도치는 이동할수 없다.
요컨데, 홍수,고슴도치,돌 등이 입력된 배열(원본 배열이라고 하겠다.)에서 홍수와 고슴도치가 시간이 지남에따라 이동하고(홍수는 상하좌우로 돌과 비버의 집을 피해 퍼져나가고) 최소시간안에 고슴도치가 비버의 집에 도달하면 되는것이다.
최소시간을 구하라는 것에서 고슴도치가 너비우선탐색을 함에 따라 거리정보를 더하여 배열의 값으로 할당해주면 되므로, 원본배열의 값을 수정하거나, 새로운 배열을 생성하여 탐색을 진행함에 따라 거리정보를 갱신해주는 방법 두가지를 떠올렸고 원본 배열의 값을 수정하게 되면 홍수의 탐색에 영향을 끼칠수도 있을것이라고 생각하여 visited라는 새로운 배열을 생성하는 것으로 방향을 잡았다. 또한 홍수가 퍼지는 모습이 원본배열을 수정하게 되면 고슴도치의 탐색에 영향을 끼칠수도 있으므로 flooded라는 홍수의 움직임을 기록해주기 위한 2차원 배열을 생성하여 홍수가 해당좌표에 도달하였다면 flooded[x][y] = True로 수정해주는 방식을 떠올렸다.
문제에서 대단히 큰 힌트를 주었는데, "고슴도치는 다음시간에 물이 찰 예정인 공간으로 이동할 수 없다"는 사실에 주목해야 한다.
이를 바꿔서 해석하면 홍수에 대한 bfs를 먼저 실시하고 고슴도치는 그 이후에 bfs를 실시하면 된다는것이다.
예를 들어 예제 입력1 에 대해 이 문제를 푼다고 가정해보자.
예제 입력 1
|
3 3
D.*
...
.S.
|
먼저 큐에 홍수(*)의 위치를 삽입하고, 이어서 고슴도치의 위치(S)를 삽입한다.
아래 그림에서 큐에 담긴 데이터중 파란색은 홍수를 의미하고, 보라색은 고슴도치를 의미하도록 하였고
visited배열은 모두 -1로 초기화하고 고슴도치의 초기위치는 0으로 설정하였다.
또한 flooded배열은 True일경우 해당자리에 홍수가 침수되었다는것을 의미하고, F는 아직 물이 닿지않았다는 것을 의미한다.
큐에 홍수의 최초좌표(0,2)와 고슴도치의 최초좌표(2,1)을 삽입하였다면, 큐에서 데이터를 팝하여 bfs를 진행한다.
홍수(0,2)가 먼저 팝되었으므로 flooded배열의 상하좌우 좌표를 문제의 조건에 맞춰 D와 X를 피하며 수정한다.
홍수는 (0,1)과 (1,2)에 이르게 되고, 위 좌표 2개를 큐에 삽입한다.
이후 다시 큐에서 데이터를 팝한다. 이번에 팝된 데이터는 고슴도치에 대한 좌표이므로 visited배열을 문제의 조건에 맞춰 수정한다.
고슴도치는 홍수에 침수되지 않은 지역과, 돌이 없는 지역으로만 이동할수 있으므로 flooded배열의 T/F여부를 확인하고 이동한다.(고슴도치는 물이 찰 예정인 공간으로도 이동할수 없으므로,홍수가 먼저 이동한후 고슴도치가 이동해도 문제와 같은 의미가 된다.)
고슴도치가 해당좌표에서 1초가 걸려 갈수있는 곳은 (2,0), (1,1), (2,2)이므로 해당 좌표를 기존 값인 0에 +1한 값인 1로 수정하고, 해당좌표들을 큐에 삽입한다.
큐에서 데이터를 팝한다. 홍수에 대한 좌표이므로 bfs하여 flooded배열을 수정한다. 이때 고슴도치가 있는 좌표를 수정해도 큰 상관이 없게 되는데, 고슴도치의 현재 위치는 확정된것이 아닌 곧 이동할것이기 때문이다. (1,1)로 홍수가 도달하게 되고 해당 좌표를 T로 수정후 큐에 삽입한다.
큐에서 데이터를 팝한다. 홍수에 대한 좌표이므로 flooded배열을 수정한다. (2,2)에 홍수가 도달하므로 T로 변경후 큐에 데이터를 삽입한다.
큐에서 데이터를 팝한다. 고슴도치에 대한 좌표이므로 visited배열을 수정한다.
1초가 지났다는 것을 파악할수있도록 기존의 값인 1에 +1한 값인 2를 해당좌표에 기록한다. 또한 해당 좌표를 큐에 삽입한다.
이어진 좌표(1,1), (2,2)에 대해서는 상하좌우로 고슴도치가 이동할수 없으므로 배열의 값과 큐의 값에 변경이 없다.
이어서 큐에서 데이터를 팝한다. 홍수에 대한 데이터이므로 flooded배열을 수정한다.
홍수는 (2,1) (1,0)에 도달하게 되고, 해당좌표의 값을 T로 수정한후 큐에 삽입한다.
이어진 좌표도 홍수에 대한 좌표이지만, 상하좌우에 이미 홍수가 도달해있으므로 값이 수정되지 않는다.
큐에서 데이터를 팝한다. 고슴도치에 대한 데이터이므로 vistied배열의 값을 수정한다. 고슴도치는 비버의굴(D)에 도달할수 있으므로 좌표의 값을 이전값인 2에 1을 더하여 3으로 수정한다. 이후 좌표를 큐에 삽입한다.
큐에서 데이터를 팝한다. 홍수에 대한 데이터이므로 flooded배열을 수정한다. 홍수는 (2,0)에 도달하게 되므로 좌표의 값을 수정하고 큐에 좌표를 삽입한다.
이어진 데이터또한 홍수에 대한 데이터이지만 상하좌우 모두 홍수가 도달하여있으므로 배열과 큐의 값을 수정하지않는다.
큐에서 데이터를 팝한다. 고슴도치에 대한 데이터이므로 visited배열의 값을 수정한다.
해당 좌표의 값이 목적지인 비버의 굴의 좌표이므로 탐색을 종료하고 해당 좌표에 대한 visited배열의 값을 리턴한다.
bfs를 모두 끝냈음에도 정답을 리턴하지 않는다면 비버의 굴에 도달하지 못하였다는 의미로 "KAKTUS" 를 리턴하도록한다.
이러한 과정을 통해 문제를 해결할수 있다.
한가지 주의해야 할 점은 홍수의 개수가 무조건 1개로 고정되는것이 아니라는 점이다.
홍수가 처음부터 아예 주어지지 않을 수도 있고, 홍수가 1개 이상으로 주어질수도 있으므로 원본배열을 탐색하며 홍수와 두더지에 대한 좌표값을 기록할때 홍수의 좌표를 배열에 기록해뒀다가 큐에 한번에 기록하는과정이 필요하다.
위 모든 과정을 코드로 옮기면 다음과 같다.
# https://www.acmicpc.net/problem/3055
'''
<탈출>
고슴도치(S)는 홍수(*)를 피해 비버(D)로 이동
S와 *는 돌(X)를 통과할수 없고, 상하좌우 인접한 공간으로 이동함
고슴도치가 비버에게 도착하는데 걸리는 최소시간을 구하라
고슴도치는 물이 찰 예정인 공간으로 이동할수 없다. 즉 다음 시간에 물이 찰 예정인 공간으로 고슴도치는 이동할수 없다.
'''
'''
고슴도치는 물이 찰 예정인 공간으로 이동할수 없다 => 물에 대하여 bfs를 먼저 실시하여라는 의미이지 않을까?
'''
# 비버가 굴로 이동할수 없다면 KAKTUS를 출력한다.
from collections import deque
r, c = map(int, input().split())
# 지도 정보 입력받기
graph = [list(input()) for _ in range(r)]
# 고슴도치(S), 홍수(*), 비버(D), 돌(X)
# 홍수의 위치를 저장할 배열
flood_array = []
# 고슴도치와 홍수의 위치 측정
for i in range(r):
for j in range(c):
if graph[i][j] == 'S':
# 고슴도치 초기위치 지정
hedgehog_x, hedgehog_y = i, j
elif graph[i][j] == '*':
# 홍수 초기위치 지정
flood_array.append([i, j])
elif graph[i][j] == 'D':
# 목적지 지정
result_x, result_y = i, j
# 큐 생성 => 홍수가 먼저 bfs를 진행하고, 이후 고슴도치의 bfs가 진행되야함
# 순서에 유의하여 큐에 삽입
queue = deque()
# 홍수에 대한 방문정보를 저장하기 위한 배열 생성
flooded = [[False]*c for _ in range(r)]
# 홍수배열에서 데이터를 뽑아서 저장
for flood_x, flood_y in flood_array:
flooded[flood_x][flood_y] = True # 홍수의 시작위치는 침수되어 있어야함
# 홍수가 먼저 탐색을 진행할수 있도록 먼저 삽입
# 세번째 인자로 True와 False를 줘서 True이면 홍수의 움직임을 의미하도록 함
queue.append([flood_x, flood_y, True])
# # 고슴도치에 대한 방문정보를 저장하기 위한 배열 => 시간을 누적시켜 저장함
visited = [[-1]*c for _ in range(r)]
visited[hedgehog_x][hedgehog_y] = 0 # 시작위치는 방문처리 시작위치에 도달하는데 걸린 시간 0초
# False이면 고슴도치의 움직임을 의미하도록
# 홍수에 대한 bfs가 선행되어야하므로, 고슴도치의 위치는 홍수의 위치를 모두 넣은 이후에 큐에 삽입
queue.append([hedgehog_x, hedgehog_y, False])
# 방향벡터 작성
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
# 홍수와, 고슴도치가 번갈아가며 이동하도록 bfs를 작성할것
def bfs(queue):
while queue:
x, y, isFlood = queue.popleft()
# 움직이는 대상이 고슴도치인지 홍수인지 구별
# 네 방향에 대해 탐색 진행
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 배열의 범위를 벗어나지 않는지와, 인접좌표가 돌이 아닌경우에 대해서 이동
if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] != 'X':
# 움직이는 대상이 홍수일경우
if isFlood:
# 이전에 방문하지 않은 정점에 대하여 flooded배열 수정
# 홍수는 비버의 집과 돌은 통과하지 못함
if not flooded[nx][ny] and graph[nx][ny] != 'D':
flooded[nx][ny] = True # 침수처리
queue.append([nx, ny, True]) # 홍수의 좌표와, 홍수여부 큐에 삽입
# 움직이는 대상이 고슴도치일경우
else:
# 고슴도치의 위치가 목적지에 도달하였다면 정답 리턴
if x == result_x and y == result_y:
return visited[x][y] # 방문하는데 걸린 시간 리턴
# 고슴도치는 침수될지역(침수된지역)으로 이동하지 못하고, 돌을 통과하지못함
# 또한 방문하지 않은 지역에 한해서 방문해야함
if not flooded[nx][ny] and visited[nx][ny] == -1: # 아직 방문하지 않은 지역에 한해서
visited[nx][ny] = visited[x][y] + 1
# 움직이는 대상이 두더지임을 큐에 삽입
queue.append([nx, ny, False])
# 비버가 도착하지 못한채 bfs가 종료되면 KAKTUS 리턴
return "KAKTUS"
print(bfs(queue))
위 코드에서는 큐에 삽입된 데이터가 홍수인지, 고슴도치인지를 구별하기 위해 큐에 좌표를 삽입할때 True와 False를 같이 삽입하는데, True라면 홍수, False라면 고슴도치라는 의미가 된다.
문제를 해결하기위한 추가 테스트 케이스도 같이 첨부하니 참고하면 문제를 해결하는데 도움이 될 것이다.
테스트 케이스는 아래 게시글에서 다운받았다.
https://www.acmicpc.net/board/view/27210
직접 풀어보기