[220925] 백준 3055 : 탈출

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

3055번: 탈출

 

※ 관련 문제

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

4179번: 불!

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

5427번: 불

1. 물과 비버의 진행 동시에 관리하기

 이 문제의 특징은 물과 비버의 움직임을 동시에 관리해야 된다는 것이다. 같은 1초 동안 움직여야 하므로, 방문 처리 함수를 하나에 관리하기에는 어려움이 있다. 따라서 본 문제에서는 보드판에는 물의 위치를 갱신해주고 비버는 방문처리 함수에서 경로를 설정해줌으로써 정답 처리를 받을 수 있도록 하였다. 이때, 물이 퍼질 예정인 곳에도 비버가 갈 수 없다는 것이 특징인데, 이와 같은 경우 물을 먼저 움직이게 해주면 같은 효과를 낼 수 있다. 비슷한 유형의 문제로는 백준 5427, 4179가 있다.

 -1) 보드판 : 물의 위치를 기록

 -2) 방문처리판 : 비버의 움직임을 기록

※ 주의 ! ※

  습관처럼 방문처리 배열을 False, True로만 기록하고 Cnt를 Q에 넣고 활용하면 틀리게 되어있다. 왜냐하면 최적점 기록을 놓친 상태로 return 으로 빠져나오는 경우가 있기 때문이다!

※ 주의 ! ※

  습관처럼 q에 비버 위치 넣고 물 함수 돌리면 안된다. 동시간대에 있는 포인트들은 전부 같은 시간동안 다 돌려야한다. 따라서, 비버가 동일 시간에 갈 수 있는 위치에 대해서 반복문을 돌린다음에 큐를 업데이트 해주어야 한다. 습관처럼 하면 무조건 틀리는 문제다.

2. 전체 코드

 메모리 : 115268 KB, 시간 : 128 ms, 풀이 시간 : 30 min

R, C = map(int, input().split())
board = [list(map(str, input())) for _ in range(R)]
visited = [[0 for _ in range(C)] for _ in range(R)]
w_info = []
sx, sy = 0, 0
ex, ey = 0, 0

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

for i in range(R):
    for j in range(C):
        if board[i][j] == '*':
            w_info.append([i, j])
        elif board[i][j] == 'D' :
            ex, ey = i, j
            board[i][j] = '.'
        elif board[i][j] == 'S' :
            sx, sy = i, j
            board[i][j] = '.'

def wateriscoming():
    size = len(w_info)
    for i in range(size):
        x, y = w_info[i][0], w_info[i][1]
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < R and 0 <= ny < C :
                if nx == ex and ny == ey :
                    continue
                if board[nx][ny] == '.' :
                    board[nx][ny] = '*'
                    w_info.append([nx, ny])
    del w_info[:size]

def beaverexodus():
    q = [[sx, sy]]
    visited[sx][sy] = 0
    wateriscoming()
    while q :
        qsize = len(q)
        for j in range(qsize):
            x, y = q[j][0], q[j][1]
            if x == ex and y == ey :
                return visited[x][y]
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny] and board[nx][ny] == '.' :
                    visited[nx][ny] = visited[x][y] + 1
                    q.append([nx, ny])
        del q[:qsize]
        wateriscoming()
    return "KAKTUS"

print(beaverexodus())