[백준] 3055번. 탈출

[백준] 3055번. 탈출 바로가기

처음 아이디어

• 처음에 물과 고슴도치의 이동 로직을 따로 둔건 한눈에 알아보기 쉽게 하려고 한거였는데 다 짜고 나니 중복도 많고 비효율적으로 짠 것 같다.

1. 물이 채워질 공간 먼저 조사하고나서 고슴도치 이동시킨다.(물이 채워질 예정인 칸은 고슴도치가 이동할 수 없기 때문이다.)

• 처음에 다음에 채워질 칸을 미리 *(물) 표시를 하려고 했는데 그랬더니
  다음에 채워질 칸에 있던(아직 물이 안온 곳) 고슴도치가 죽어서
  그냥 다음에 채워질 칸들은 덱에 넣어놓고 고슴도치가 이동하려는 방향이
  물이 찰 예정인 칸과 같다면 이동못하게 했다.

2. 고슴도치가 이동할 수 있는 방향으로 이동시킨다.
   2-1. 다음번에 물이 채워질 칸으로 이동할 수 없다.
3. 물을 이동시키고 다음에 채워질 칸을 덱에 넣는다.

결과

계속 시간초과에 메모리 초과 떠서 한시간을 디버깅했지만 해결하지 못했다. -> 탈출 못함

문제가 된 부분

x, y = water_list.popleft()
tiddup_forest[x][y] = '*'

• 고슴도치 이동과 다르게 물 이동 bfs에서 물이 이동할 때 방문처리를 해줘서 시간이 오래걸리는 거였다.
• visited를 만들고 nx, ny를 조사할 때 방문이 된 것들은 방문하지 않는다.

if 0 <= nx < r and 0 <= ny < c and tiddup_forest[nx][ny] != 'D' and tiddup_forest[nx][ny] != 'X' and not visited[nx][ny]:
	water_list.append((nx, ny))
    visited[nx][ny] = 1

시간복잡도

• O(r * c)

코드

from collections import deque
import sys
input = sys.stdin.readline


# 물은 매 분마다 비어있는 칸으로 확장한다. (X, D)는 이동 불가능.
def water(water_list, w_cnt):

    # 물의 개수만큼만 물이 찰 예정인 칸 조사한다.
    while w_cnt > 0:
        w_cnt -= 1
        x, y = water_list.popleft()
        tiddup_forest[x][y] = '*'

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < r and 0 <= ny < c and tiddup_forest[nx][ny] != 'D' and tiddup_forest[nx][ny] != 'X' and not visited[nx][ny]:
                water_list.append((nx, ny))
                visited[nx][ny] = 1
    
    return water_list


# 고슴도치는 인접한 네칸 중 하나로 이동할 수 있다. (*, X)는 이동 불가능.
# + 물이 찰 예정인 칸으로 이동할 수 없다.
def gosumdochi(move_list, move_cnt):
    global result

    while move_cnt > 0:
        move_cnt -= 1
        x, y, time = move_list.popleft()

        # 이미 물이 찬 지역이면 없던걸로 한다
        if tiddup_forest[x][y] == '*':
            continue
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < r and 0 <= ny < c:
                if tiddup_forest[nx][ny] == 'D':
                    print(time + 1)
                    exit(0)
                
                elif tiddup_forest[nx][ny] != 'X' and tiddup_forest[nx][ny] != '*' and tiddup_forest[nx][ny] != 'S' and tiddup_forest[nx][ny] not in water_list:
                    move_list.append((nx, ny, time + 1))
                    tiddup_forest[nx][ny] = 'S'
                    visited[nx][ny] = 1


r, c = map(int, input().split())
tiddup_forest = [list(input().strip()) for _ in range(r)]
move_list = deque([])
water_list = deque([])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[0] * c for _ in range(r)]

# 고슴도치 위치와 물의 위치 찾기
for i in range(r):
    for j in range(c):
        if tiddup_forest[i][j] == 'S':
            move_list.append((i, j, 0))
        elif tiddup_forest[i][j] =='*':
            water_list.append((i, j))


while move_list:
    # 이동하기 전에 물이 찰 공간 체크
    w_cnt = len(water_list)

    if water_list:
        water(water_list, w_cnt)

    # 고슴도치 이동
    move_cnt = len(move_list)
    gosumdochi(move_list, move_cnt)


print("KAKTUS")

두번째 아이디어

• 고슴도치와 물을 같은 덱에 담는다.
  -> 고슴도치가 물이 찰 예정인 칸에 못가는 것은 물에 잠기기 때문이다
  -> 그냥 물에 잠기게 하면 그쪽으로 이동 안하면 되니까
  -> 고슴도치를 먼저 덱에 넣어서 이동시킨 후, 물을 이동시킨다.

• 각 거리는 visited를 이용해서 체크해준다.

문제점

• 고슴도치 위치를 먼저 담고싶었지만 이중 for문을 돌리다가 먼저 나오는 거 먼저 담는다 -> appendleft를 알게 되었다(왼쪽 끝에 원소를 입력한다.)

코드

from collections import deque
import sys
input = sys.stdin.readline

# 이동
def move(q):
    while q:
        x, y = q.popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < r and 0 <= ny < c:
                # 고슴도치일 때(물, 돌, 방문했던 곳 X)
                if tiddup_forest[x][y] == 'S':
                    if tiddup_forest[nx][ny] == 'D':
                        return visited[x][y] + 1
                    
                    elif tiddup_forest[nx][ny] != 'X' and tiddup_forest[nx][ny] != '*' and not visited[nx][ny]:
                        visited[nx][ny] = visited[x][y] + 1 # 방문처리 + 거리
                        tiddup_forest[nx][ny] = 'S'
                        q.append((nx, ny))
                
                # 물일 때(비버굴, 돌, 방문했던 곳 X)
                else:
                    if tiddup_forest[nx][ny] != 'D' and tiddup_forest[nx][ny] != 'X' and tiddup_forest[nx][ny] != '*':
                        tiddup_forest[nx][ny] = '*'          # 방문처리
                        q.append((nx, ny))
    
    return "KAKTUS"


r, c = map(int, input().split())
tiddup_forest = [list(input().strip()) for _ in range(r)]
q = deque([])
visited = [[0] * c for _ in range(r)] # 각 위치별 거리
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(r):
    for j in range(c):
        if tiddup_forest[i][j] == 'S':
            q.appendleft((i, j))
        elif tiddup_forest[i][j] =='*':
            q.append((i, j))

print(move(q))