따봉도치는 고마워! (백준 3055:탈출)

3055번: 탈출 (acmicpc.net)

3055번: 탈출

 

여러분들은 인터넷하면서 많은 낚시글을 본적이 있을 것이다. (본적없다면 당신은 상당히 건실한 삶을 살았다는 것이다. 자랑스러워해도 된다.)

 

이런 고전짤로부터 시작해서

 

 

소중한 머리카락으로 협박하는 놈도 있었고

 

 

 

여러분의 관심사와 흥미를 빅 데이터로 분석하여 가장 높은 조회수를 이끌어낼 만한 제목을 도출했습니다

같은 대 인공지능 시대에 걸맞는 낚시글도 있었고,

 

 

최근에 유행했던 킹치만이나 가슴이 웅장해지는 구미호놈까지

인터넷이 존재하는 한, 낚시글은 끊이지 않을 것이다.

 

 

따봉도치야 고마워!

물론 인터넷보면서 이런 식의 낚시글을 본게 한두개가 아니지만 (자라나라머리머리의 탈모 저주글을 포함하여)

그럼에도 불구하고 따봉도치는 보는 사람도 훈훈해지고 따봉하는 고슴도치가 귀여워서 인상에 남았다.

 

 

그러면 이번 글의 제목은 따봉도치는 고마워인데 왜 고마워할까?

문제를 보도록하자.

 

 

 민혁이가 인터넷을 하다가 낚시글때문에 화가 굉장히 많이 났나보다.

특히 민혁이가 탈모빔을 맞았다면 이해할 법도 한다. (마법 구슬도 탈모는 못고치나보다.)

 

하지만 따봉도치는 착하고 귀여운 존재이니 따봉도치가 도망칠 수 있도록 해보자.

 

사실 이 문제는 BFS를 살짝 응용한 문제이다.

(BFS 기본 문제는 다음을 참고하자. 2020/12/29 - [앨고리뜸/백뚠] - 미노타우르스와 함께 춤을 (백준 2178:미로탐색))

 

 

그러면 바로 입력을 받아보자.

import sys
from collections import deque

R, C = map(int,sys.stdin.readline().split())

forest= []
check_water = deque([])
check_hedgedog = deque([])
minute = 1

for r in range(R):
    temp = list(str(sys.stdin.readline().rstrip()))
    forest.append(temp)
    if "*" in temp:
        check_water.append([r,temp.index("*"), minute])
    if "S" in temp:
        check_hedgedog.append([r,temp.index("S"), minute])

 

우선, 입력을 str으로 바꾼 뒤, 한글자한글자 요소로 삼는 리스트로 저장했다. 

그리고 나중에 for문을 2번 돌리고 최초 물의 위치와 고슴도치 위치를 파악하는 수고를 덜기위해서, 입력단계에서 물의 위치를 입력을 받으면서 저장하도록 했다.

 

그리고 물(check_water)과 고슴도치(check_hedgedog) 을 따로 받는 것이 보일 것이다.

각각의 개체에 대해서 BFS를 진행할 것이기 때문에 따로 deque를 만들어 주었다.

 

그럼 BFS를 진행해보자.

 

"고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다." 라는 조건이 있기 때문에 물을 먼저 움직여줘야한다.

while check_hedgedog:
    while check_water and check_water[0][2] == minute:
        water_node = check_water.popleft()
        water_x = water_node[0]
        water_y = water_node[1]
        
        for d in range(4):
            water_nx = water_x + dx[d]
            water_ny = water_y + dy[d]

            if 0 <= water_nx < R and 0 <= water_ny < C:
                if forest[water_nx][water_ny] == "." or forest[water_nx][water_ny] == "S":
                    check_water.append([water_nx,water_ny, minute+1])
                    forest[water_nx][water_ny] = "*"

여기서 미로탐색 때와는 다르게 for문이 아니라 while을 쓴 것을 알 수있다.

for문이나 while이나 그렇게 차이나지 않지만, 이번에는 while을 써보기로 했다.

 

또한, 문제에는 명시되어있지 않지만, 물이 아예 없을 수도 있다. 그렇기 때문에 if + for 쓰기 보다는 while을 썼다.

 

단, while을 쓰기 위해서는 check에 저장할 때, 좌표 뿐만 아니라 어느 단계에서 이 좌표에 대해 탐색을 할 것인지에 대한 정보도 같이 넣어줘야한다.

 

만약 좌표만 넣어준 경우에는 고슴도치는 움직이지 않은 채, 물만 계속해서 확장할 가능성이 있다.

그래서 이번에는 [ water_nx (새로운 물의 x좌표), water_ny (새로운 물의 y좌표), minute+1 ( 어느 minute 때 이 좌표를 기준으로 탐색할 것인가) ] 를 넣어주었다.

 

 

그리고 물의 턴이 끝났으면, 고슴도치의 턴을 설정해주자.

 

while check_hedgedog and check_hedgedog[0][2] == minute:
        hedgedog_node = check_hedgedog.popleft()
        hedgedog_x = hedgedog_node[0]
        hedgedog_y = hedgedog_node[1]
        
        for d in range(4):
            hedgedog_nx = hedgedog_x + dx[d]
            hedgedog_ny = hedgedog_y + dy[d]

            if 0 <= hedgedog_nx < R and 0 <= hedgedog_ny < C:
                if forest[hedgedog_nx][hedgedog_ny] == "D":
                    print(hedgedog_node[2])
                    exit()
                elif forest[hedgedog_nx][hedgedog_ny] == "." :
                    check_hedgedog.append([hedgedog_nx,hedgedog_ny,hedgedog_node[2]+1])
                    forest[hedgedog_nx][hedgedog_ny] = "S"
        
    minute += 1

고슴도치가 친구 비버의 굴을 찾았을 때, 종료하는 것 빼고는 비슷하다.

 

그리고, 만약 물이 비버로 가는 모든 경로를 막아버렸을 경우에 고슴도치는 불쌍하게도 최후를 맞이하게 될 것이다.

 

이 결말의 조건은 check_hedgedog에 더이상 갈 경로가 존재하지 않을 경우 (사방이 돌이나 물로 막혀있을 경우)가 된다.

물의 BFS 코드에서 첫번째 while을 기억하는가?

 

while check_hedgedog: 가 되어있었다.

check_hedgedog이 있다면 고슴도치는 계속 살길을 도모해보겠지만 그렇지 않다면, 고슴도치는 최후를 맞이하고 KAKATUS를 띄워줘야한다. (Kakatus는 선인장이라는 뜻이다. 우리는 이로인해 민혁이가 얼마나 악질인가를 알 수있다.)

 

전체코드는 다음과 같다.

 

import sys
from collections import deque

R, C = map(int,sys.stdin.readline().split())

forest= []
check_water = deque([])
check_hedgedog = deque([])
minute = 1

for r in range(R):
    temp = list(str(sys.stdin.readline().rstrip()))
    forest.append(temp)
    if "*" in temp:
        check_water.append([r,temp.index("*"), minute])
    if "S" in temp:
        check_hedgedog.append([r,temp.index("S"), minute])

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


while check_hedgedog:
    while check_water and check_water[0][2] == minute:
        water_node = check_water.popleft()
        water_x = water_node[0]
        water_y = water_node[1]
        
        for d in range(4):
            water_nx = water_x + dx[d]
            water_ny = water_y + dy[d]

            if 0 <= water_nx < R and 0 <= water_ny < C:
                if forest[water_nx][water_ny] == "." or forest[water_nx][water_ny] == "S":
                    check_water.append([water_nx,water_ny, minute+1])
                    forest[water_nx][water_ny] = "*"



    while check_hedgedog and check_hedgedog[0][2] == minute:
        hedgedog_node = check_hedgedog.popleft()
        hedgedog_x = hedgedog_node[0]
        hedgedog_y = hedgedog_node[1]
        
        for d in range(4):
            hedgedog_nx = hedgedog_x + dx[d]
            hedgedog_ny = hedgedog_y + dy[d]

            if 0 <= hedgedog_nx < R and 0 <= hedgedog_ny < C:
                if forest[hedgedog_nx][hedgedog_ny] == "D":
                    print(hedgedog_node[2])
                    exit()
                elif forest[hedgedog_nx][hedgedog_ny] == "." :
                    check_hedgedog.append([hedgedog_nx,hedgedog_ny,hedgedog_node[2]+1])
                    forest[hedgedog_nx][hedgedog_ny] = "S"
        
    minute += 1

print("KAKTUS")

BFS를 동시에 두군데서 진행해야된다는 것을 빼면 미로탐색과 동일한 문제였다.

 

우리 친구 고슴도치는 무사히 친구 비버의 굴로 도망칠 수 있었다.

 

 

 

무사히 길을 안내해주자 따봉도치가 고마워한다.

다들 따봉도치의 행운을 받고 코로나 걸리는 일 없이 건강하게 2021년을 살아갔으면 좋겠다.