[백준 3055번] 탈출

📎 문제링크

백준 3055번

🤔 문제 이해 및 알고리즘 유형

비버와 물이 동시에 상하좌우로 이동한다.
이때

1) 비버는 물과 바위를 뛰어 넘을 수 없음
2) 물은 둥지와 바위를 덮을 수 없음

결과적으로 비버가 둥지에 도착하는 가장 최소 시간을 구하는 문제

알고리즘 유형
BFS

💡 문제 해결 방법

1. 물과 비버가 동시에 이동해야 하기 때문에 큐를 2개로 설정해서 저장
   1) roadmap을 먼저 탐색하면서 물이 나오면 water 큐에 삽입
   2) 비버의 위치가 나오면 start 지점으로 저장 or q(큐)에 삽입
   3) D(둥지의 위치)가 나오면 end 지점으로 저장
2. bfs를 수행 -> 비버와 물이 동시에 이동하는게 포인트!!
   1) 물을 따로 bfs 수행
   2) 비버도 따로 bfs 수행

💻 코드

• 처음 작성한 코드

import sys
from collections import deque
input = sys.stdin.readline
R,C = map(int,input().split())
roadmap = [list(input().strip()) for _ in range(R)]
#비버의 굴 D, 고슴도치의 위치 S
#돌은 x, 물이 차있는 지역 *
#위,아래,오른쪽,왼쪽->물과 고슴도치 이동 가능
water = deque()

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


for i in range(R):
    for j in range(C):
        if roadmap[i][j]=="S":
            start_x,start_y = i,j
        elif roadmap[i][j]=="D":
            end_x,end_y = i,j
        elif roadmap[i][j]=="*":
            water.append((i,j))

def water_bfs():
    num = len(water)
    for _ in range(num):
        w_x,w_y= water.popleft()
        for i in range(4):
            wx,wy=w_x+dx[i],w_y+dy[i]
            if 0<=wx<R and 0<=wy<C and roadmap[wx][wy]==".":
                roadmap[wx][wy]="*"
                water.append((wx,wy))



def bfs(start_x,start_y):
    q=deque()
    q.append((start_x,start_y))
    roadmap[start_x][start_y]=0
    result=False
    while q:
        water_bfs()
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<R and 0<=ny<C and roadmap[nx][ny]!="*" and roadmap[nx][ny]!="X":
                if roadmap[nx][ny]==".":
                    q.append((nx,ny))
                    roadmap[nx][ny]=roadmap[x][y]+1
                elif roadmap[nx][ny]=="D":
                    result=True
                    roadmap[nx][ny]=roadmap[x][y]+1
                    break
    if result == False:
        return 0
    else:
        return roadmap[end_x][end_y]






status = bfs(start_x,start_y)
if status==0:
    print("KAKTUS")
else:
    print(status)

• 처음 작성한 코드에서 틀린 점

1. 비버와 물이 동시에 이동하지 않은 것 -> 처음코드에서는 물을 먼저 이동시킨 후 고슴도치를 이동시킴
2. 반복문 사용 -> water_bfs에서만 while문 안에 for문을 작성하고 비버_bfs에서는 while문안에 for문을 작성해주지 않아 여러 경우를 고려하지 않았음

👍 정답 코드

• chatGPT와 함께 한 코드 ㅋㅋㅋ

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

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

water = deque()
q = deque()

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

for i in range(R):
    for j in range(C):
        if roadmap[i][j] == "S":
            q.append((i, j))
        elif roadmap[i][j] == "D":
            end_x, end_y = i, j
        elif roadmap[i][j] == "*":
            water.append((i, j))


def water_bfs():
    num = len(water)
    for _ in range(num):
        w_x, w_y = water.popleft()
        for i in range(4):
            wx, wy = w_x + dx[i], w_y + dy[i]
            if 0 <= wx < R and 0 <= wy < C and roadmap[wx][wy] == ".":
                roadmap[wx][wy] = "*"
                water.append((wx, wy))


def bfs():
    time = 0
    while q:
        water_bfs()
        size = len(q)
        for _ in range(size):#동시에 이동하기 위해서는 반복문 사용해줘야함
            x, y = q.popleft()
            if x == end_x and y == end_y:
                return time
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if 0 <= nx < R and 0 <= ny < C and (roadmap[nx][ny] == "." or roadmap[nx][ny] == "D"):
                    roadmap[nx][ny] = "S"
                    q.append((nx, ny))
        time += 1#시간마다 이동하므로 반복문이 끝난 후에 time +=1 동작
    return "KAKTUS"


result = bfs()
print(result)

✔ 생각해봐야 할 점

동시에 이동할 때 어떻게 코드를 짜야할 지 고민해봐야겠다. while문 안에 큐의 길이만큼 반복문을 돌면서 이동하는 방법을 항상 생각해보자!
결론 - chatGPT 사랑해요