[백준/G4] 탈출

이 문제를 풀 때 주의할 점은 고슴도치가 이동하기 전에 물이 먼저 번져야 한다는 것이다.

이는 시간(혹은 레벨)별로 구분해서 처리를 할 필요가 있다는 것이다.

 

즉 매 시간마다 물 먼저, 고슴도치는 나중에 처리를 하도록 해야한다.

이 방법을 고민하다가, 큐를 한 개 쓰는 방법, 그리고 두 개 쓰는 방법을 생각해 풀이해 보았는데

 

결국 FIFO라는 큐의 특성 때문에, 물 웅덩이가 몇개로 시작하든 한 단계(하나의 시간)에서 물이 다 퍼지고 나서 

고슴도치가 이동할 수 있도록 하는 것에는 변함이 없다.

 

간결함은 주석 처리된 1번째 코드를, 이해하기에는 2번째 코드가 더 좋은 것 같다. 

성능은 두 코드가 거의 비슷했다.

 

# from collections import deque

# R, C = map(int, input().split())
# grid = []
# for _ in range(R):
#     grid.append(list(input().strip()))

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

# q = deque()
# visit = [[False] * C for _ in range(R)]

# # 물의 위치들을 먼저 큐에 넣기
# for i in range(R):
#     for j in range(C):
#         if grid[i][j] == '*':
#             q.append(('*', i, j, 0))

# # 고슴도치 위치 넣기
# for i in range(R):
#     for j in range(C):
#         if grid[i][j] == 'S':
#             q.append(('S', i, j, 0))
#             visit[i][j] = True

# while q:
#     type, cy, cx, time = q.popleft()
    
#     if type == '*':  # 물 처리
#         for i in range(4):
#             ny, nx = cy + dy[i], cx + dx[i]
#             if 0 <= ny < R and 0 <= nx < C and grid[ny][nx] == '.':
#                 grid[ny][nx] = '*'
#                 q.append(('*', ny, nx, time + 1))
    
#     else:  # 고슴도치 처리
#         if grid[cy][cx] == 'D':  # 도착
#             print(time)
#             exit()
        
#         for i in range(4):
#             ny, nx = cy + dy[i], cx + dx[i]
#             if 0 <= ny < R and 0 <= nx < C and not visit[ny][nx]:
#                 if grid[ny][nx] == '.' or grid[ny][nx] == 'D':
#                     visit[ny][nx] = True
#                     q.append(('S', ny, nx, time + 1))

# print("KAKTUS")

from collections import deque

R,C= map(int,input().split())
grid=[]

for _ in range(R):
    grid.append(list(input().strip()))

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

water_q= deque()
hedgehog_q= deque()

#물과 고슴도치 위치 찾기

for i in range(R):
    for j in range(C):
        if grid[i][j]=="*":
            water_q.append((i,j))
        elif grid[i][j]=="S":
            hedgehog_q.append((i,j))

visit= [[False] * C for _ in range(R)]

# 고습도치 시작점 방문처리
for i in range(R):
    for j in range(C):
        if grid[i][j]=="S":
            visit[i][j]=True
            break

time=0

# 조건은 고슴도치가 움직일 수 있을 때
while hedgehog_q:
    time+=1

    #1단계: 물 먼저 퍼뜨리기
    water_size= len(water_q)
    for _ in range(water_size):
        cx,cy= water_q.popleft()

        for i in range(4):
            nx,ny=cx+dx[i], cy+dy[i]
            if 0 <= nx < R and 0 <= ny < C and grid[nx][ny] == '.':
                grid[nx][ny]="*"
                water_q.append((nx,ny))

    hedgehog_size= len(hedgehog_q)
    for _ in range(hedgehog_size):
        cx,cy= hedgehog_q.popleft()

        for i in range(4):
            nx, ny= cx+dx[i], cy+dy[i]
            if 0 <= nx < R and 0 <= ny < C and not visit[nx][ny]:
                if grid[nx][ny]=="D":
                    print(time)
                    exit()
                elif grid[nx][ny]==".":
                    visit[nx][ny]=True
                    hedgehog_q.append((nx,ny))
    

print("KAKTUS")

 

---

0922 수정

 

큐를 하나 사용하는 방법을 연구하다가 중요한 내용이 빼먹어서,,,

주석 처리된 코드를 보면 큐를 하나 사용할 때는 물인지, 고슴도치인지를 나타내는 타입까지 함께 큐 안에 저장해주어야 했다.

그 이유는 타입을 알 수 없다면 마지막 D에 도달할 때 그게 고슴도치가 도착한 것인지 물이 도착한 것인지 알 수 없기 때문에,

좀 더 복잡한 처리를 해줘야 한다.

 

 

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

R, C = map(int, input().split())
li = []
for _ in range(R):
    li.append(list(input().strip()))

q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visit = [[False] * C for _ in range(R)]

# 물 먼저 큐에 넣기
for i in range(R):
    for j in range(C):
        if li[i][j] == '*':
            q.appendleft((i, j, 0))
        if li[i][j] == "S":
            q.append((i, j, 0))
            visit[i][j] = True

while q:
    cx, cy, ctime = q.popleft()
    
    # 고슴도치가 D에 도달했는지 체크 (이동하기 전에 체크)
    if li[cx][cy] == 'D':
        print(ctime)
        exit()

    for i in range(4):
        nx = cx + dx[i]
        ny = cy + dy[i]

        if 0 <= nx < R and 0 <= ny < C and not visit[nx][ny]:
            if li[cx][cy] == '*':  # 물 처리
                if li[nx][ny] == '.':  # 물은 빈 공간으로만 퍼짐
                    visit[nx][ny] = True
                    li[nx][ny] = '*'
                    q.append((nx, ny, ctime + 1))
                    
            elif li[cx][cy] == 'S':  # 고슴도치 처리
                if li[nx][ny] == '.' or li[nx][ny] == 'D':
                    visit[nx][ny] = True
                    if li[nx][ny] == '.':  # 빈 공간일 때만 S로 변경
                        li[nx][ny] = 'S'
                    # D일 때는 격자를 수정하지 않음
                    q.append((nx, ny, ctime + 1))

print("KAKTUS")

 

이 방법보다는 확실히 타입을 명시하는 것이 좋은 방법이라고 생각했다.