[백준] 3055 탈출 python3

문제 :  https://www.acmicpc.net/problem/3055

3055번: 탈출

대충 이민혁씨가 잘못했다는 내용

 

코드

from collections import deque

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


def bfs(type, starts):
    queue = deque()
    queue.extend(starts)

    while queue:
        cx, cy = queue.popleft()
        for d in range(len(dx)):
            nx = dx[d] + cx
            ny = dy[d] + cy
            if 0 <= nx < R and 0 <= ny < C:
                if type == 'w':
                    # 물이 차는 시간 채우기
                    if forest[nx][ny] not in 'XD' and water_time[nx][ny] == -1:
                        water_time[nx][ny] = water_time[cx][cy] + 1
                        queue.append((nx, ny))

                elif type == 'd':
                    # 도치가 이동하는 시간 채우기
                    if forest[nx][ny] == 'D': # 도달한 경우
                        dochi_time[nx][ny] = dochi_time[cx][cy] + 1
                        return

                    if forest[nx][ny] == '.' and dochi_time[nx][ny] == -1 and \
                            (dochi_time[cx][cy] + 1 < water_time[nx][ny] or water_time[nx][ny] == -1):
                        dochi_time[nx][ny] = dochi_time[cx][cy] + 1
                        queue.append((nx, ny))


R, C = map(int, input().split(" "))
forest = [input() for _ in range(R)]
sx, sy = -1, -1
ex, ey = -1, -1
waters = []

water_time = [[-1]*C for _ in range(R)]
dochi_time = [[-1]*C for _ in range(R)]

# 초기화
for r in range(R):
    for c in range(C):
        if forest[r][c] == '*':
            waters.append((r, c))
            water_time[r][c] = 0
        elif forest[r][c] == 'S':
            sx, sy = r, c
            dochi_time[sx][sy] = 0
        elif forest[r][c] == 'D':
            ex, ey = r, c

bfs('w', waters)
bfs('d', [(sx, sy)])

if dochi_time[ex][ey] == -1:
    print('KAKTUS')
else:
    print(dochi_time[ex][ey])

 

해설

생각해야 할 조건은 다음과 같다.

1. 고슴도치는 물이 찼거나 곧 찰 예정인 곳에 가지 못한다.
2. 물은 돌과 비버의 굴로 갈 수 없다.
3. 고슴도치는 돌에 갈 수 없다.

bfs를 두번 돌리는 방법으로 풀었다.

첫번째 bfs를 통해 물이 찰 곳과 차는데 걸리는 시간을 구했고 (water_time), 

두번째 bfs를 통해 고슴도치가 지나갈 수 있는 장소를 구하였다 (dochi_time).

 

계속 메모리 누수가 나길래 자료구조를 잘못 선택했나, 비효율적으로 돌렸나 싶었지만 그게 아니었던 모양이다.

고슴도치가 지나갈 수 있는 장소의 조건은 다음과 같다.

1. 물이 이미 찬 곳은 지나갈 수 없다. (water_time == -1)
2. 물이 다음 턴에 찰 곳은 지나갈 수 없다. (dochi_time + 1 < water_time)
3. 돌은 지나갈 수 없다. (forest != 'X')
4. 이미 지나간 곳은 지나갈 수 없다. (dochi_time == -1)

4번째 조건을 추가했더니 메모리 누수가 사라졌다.

아마 조건을 헐렁하게 해버려서 불필요한 반복이 생긴게 아니었을까 싶다.