[백준3055/골4] 탈출 - Python

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

 

 

 

처음엔

1. 물이 퍼지는 시간 지도에 너비우선탐색으로 갱신 (while water)

2. 고슴도치가 너비우선탐색으로 이동하면서 도착하면 걸린시간 출력 후 exit

3. 2번에서 while문 다 끝나도 도착 못하면 print('KAKTUS')

하면되는 단순한 문제라고 생각했다.

 

실패 코드

from collections import deque

# . : 비어있는곳, * : 물, X : 돌, D : 도착, S : 시작


R, C = map(int, input().split())  # R행, C열
forest = [list(input()) for _ in range(R)]

start = deque([])
end = (0, 0)
water = deque([])

# 지도 위치 기록
for i in range(R):
    for j in range(C):

        if forest[i][j] == '*':
            water.append((i, j, 0))
        elif forest[i][j] == 'S':
            start.append((i, j, 0))
        elif forest[i][j] == 'D':
            end = (i, j)


# 물 차오르는 곳 먼저 전부 지도에 갱신
while water:

    cr, cc, ct = water.popleft()

    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        nr, nc = cr + di, cc + dj

        if 0 <= nr < R and 0 <= nc < C and forest[nr][nc] == '.':
            forest[nr][nc] = ct + 1
            water.append((nr, nc, ct + 1))


visited = [[False] * C for _ in range(R)]
visited[start[0][0]][start[0][1]] = 0

# 고슴도치 이동
while start:

    cr, cc, ct = start.popleft()

    if (cr, cc) == end:
        print(ct)
        exit(0)


    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        nr, nc = cr + di, cc + dj

        # 고슴도치가 이동 가능할 -> 여기서 실수 발생!
        if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc] and isinstance(forest[nr][nc], int) and forest[nr][nc] > ct + 1:
            visited[nr][nc] = ct + 1
            start.append((nr, nc, ct + 1))

        # 고슴도치가 도착함
        if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc] and forest[nr][nc] == 'D':
            visited[nr][nc] = ct + 1
            start.append((nr, nc, ct + 1))

print('KAKTUS')

 

고슴도치가 이동 가능할 때 isinstance 함수로 int인지 조건 검사해서 int일 때만 이동하도록 했는데 "." 일때(물이 차오르지 않는 부분)도 이동 가능한 걸 놓쳤다.

 

 

성공 코드 1

from collections import deque

# . : 비어있는곳, * : 물, X : 돌, D : 도착, S : 시작


R, C = map(int, input().split())  # R행, C열
forest = [list(input()) for _ in range(R)]

start = deque([])
end = (0, 0)
water = deque([])

for i in range(R):
    for j in range(C):

        if forest[i][j] == '*':
            water.append((i, j, 0))
        elif forest[i][j] == 'S':
            start.append((i, j, 0))
        elif forest[i][j] == 'D':
            end = (i, j)


# 물 차오르는 곳 먼저 전부 지도에 저장
while water:

    cr, cc, ct = water.popleft()

    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        nr, nc = cr + di, cc + dj

        if 0 <= nr < R and 0 <= nc < C and forest[nr][nc] == '.':
            forest[nr][nc] = ct + 1
            water.append((nr, nc, ct + 1))


visited = [[False] * C for _ in range(R)]
visited[start[0][0]][start[0][1]] = 0

# 고슴도치 이동
while start:

    cr, cc, ct = start.popleft()

    if (cr, cc) == end:
        print(ct)
        exit(0)


    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        nr, nc = cr + di, cc + dj

        # 고슴도치가 이동 가능할 때 ('X'만 아니면 다 이동 가능)
        if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc] and forest[nr][nc] != 'X':
			
            # 문자열(빈공간 또는 도착지점) 일 때 방문처리 후 append
            if forest[nr][nc] == '.' or forest[nr][nc] == 'D':
                visited[nr][nc] = ct + 1
                start.append((nr, nc, ct + 1))
			
            # 물이 차오른곳(int) 이면서 고슴도치 이동보다 물이 늦게 차오른다면, 방문처리 후 append
            elif isinstance(forest[nr][nc], int) and forest[nr][nc] > ct + 1:
                visited[nr][nc] = ct + 1
                start.append((nr, nc, ct + 1))

print('KAKTUS')

 

이렇게 고쳤더니 성공했다.

근데 하다보니 지도에서 처리할 조건이 너무 많아서 그냥 물이 차오른 시간을 따로 저장해서 풀어봤다.

 

성공코드2

from collections import deque

# . : 비어있는곳, * : 물, X : 돌, D : 도착, S : 시작


R, C = map(int, input().split())  # R행, C열
forest = [list(input()) for _ in range(R)]

start = deque([])
end = (0, 0)
water = deque([])

water_time = [[float('inf')] * C for _ in range(R)]
visited = [[False] * C for _ in range(R)]

for i in range(R):
    for j in range(C):

        if forest[i][j] == '*':
            water.append((i, j, 0))
            water_time[i][j] = 0
        elif forest[i][j] == 'S':
            start.append((i, j, 0))
            visited[i][j] = True
        elif forest[i][j] == 'D':
            end = (i, j)


# 물 차오르는 곳 먼저 전부 water_time 2차원 배열에 따로 저장
while water:

    cr, cc, ct = water.popleft()

    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        nr, nc = cr + di, cc + dj

        if 0 <= nr < R and 0 <= nc < C and forest[nr][nc] == '.' and water_time[nr][nc] == float('inf'):
            water_time[nr][nc] = ct + 1
            water.append((nr, nc, ct + 1))


# 고슴도치 이동
while start:

    cr, cc, ct = start.popleft()

    # 도착이면 마무리
    if (cr, cc) == end:
        print(ct)
        exit(0)

    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        nr, nc = cr + di, cc + dj

        # 고슴도치가 이동 가능할 때
        if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc] and (forest[nr][nc] == '.' or forest[nr][nc] == 'D'):

            # 도착이거나, 아직 물에 차치않은 곳이면 방문처리, append
            if forest[nr][nc] == 'D' or water_time[nr][nc] > ct + 1:
                visited[nr][nc] = True
                start.append((nr, nc, ct + 1))


print('KAKTUS')

 

물이 차오른 곳 float('inf')로 초기 설정하고 하니까 좀 더 간단하고 좋은듯~