[python] 백준 3055 :: 탈출 (BFS)

2023. 3. 21. 14:20Algorithm

728x90
반응형

[탈출]

# 문제
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

# 입력
첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

# 출력
첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

굉장히 씹덕같지만 귀여운 문제👾

0. 풀이 방법

  • 물이 차오르는 곳은 고슴이가 이동할 수 없으니
    물을 먼저 불리고 고슴이를 이동시킨다.

  • 고슴이와 물의 좌표를 기준으로 상하좌우를 탐색한다.

  • 상하좌우를 탐색할 때
    고슴이와 물 모두 갈 수 없는 을 무시하고,
    고슴이는 가지 못하고 물은 또 갈 필요가 없는 도 무시한다.

  • 고슴이가 이동할 때마다 도착한 좌표에 시간을 1씩 추가하며 저장해둔다.

  • 고슴이가 비버네 도착했을 때 저장해둔 시간을 출력하면 끝!


1. 방문 체크 리스트 만들기

  • 방문 체크 배열은 -1로 초기화한다.

  • 방문 체크 & 시간 저장 용도로 사용할 예정
    (고슴이의 첫 위치를 0으로 바꾸고 1씩 증가시켜 줄 거임)

    visited = [[-1] * C for _ in range(R)]

2. 물과 고슴이의 좌표를 찾는다.

  • 물을 먼저 불리고 고슴이를 이동시킬 거니까
    물은 queue의 앞부분에 넣고(appendleft)
    고슴이는 뒤에 넣는다.(append)

  • visited 리스트에서 고슴이 좌표에 0으로 시간을 저장해둔다.

for y in range(R):
    for x in range(C):
        if map[y][x] == '*':  # 물 좌표를 앞에 추가
            q.appendleft((y, x))
        elif map[y][x] == 'S':  # 고슴이 좌표 추가
            q.append((y, x))
            visited[y][x] = 0  # 출발점에 시간 0 저장

3. 큐에서 앞에서부터 하나씩 꺼내서 상하좌우를 탐색한다.

  • 상하좌우 탐색 준비!
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

while q:
    y, x = q.popleft()
    cur = map[y][x]  # 현재 위치
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]  # 다음에 갈 좌표

4. 다음 좌표 중 탐색할 필요가 없는 곳을 먼저 거른다.

갈 필요 없는 곳

1) 좌표가 map의 범위를 벗어나는 경우
2) 고슴이가 이미 방문한 곳
3) 물 👉 고슴이는 갈 수 없고, 물은 이미 물이니까 갈 필요 X
4) 돌 👉 고슴이도 물도 못 감
5) 물은 비버네 못 감

        if ny < 0 or ny >= R or nx < 0 or nx >= C:  # 범위 밖이면 무시
            continue
        if visited[ny][nx] != -1:  # 이미 방문한 곳 무시
            continue
        if map[ny][nx] == "*":  # 물 무시
            continue
        if map[ny][nx] == "X":  # 돌 무시
            continue
        if cur == "*" and map[ny][nx] == "D":  # 물이 비버네 가려면 무시
            continue

5. 고슴이의 다음 좌표

  • 고슴이가 가려는 다음 좌표가 비버네면 도착! 출력하고 for문을 탈출한다. (break)

  • 고슴이가 가려는 다음 좌표가 비버네가 아니라면
    방문 체크 배열에 시간을 저장한다.
    (현재 위치에 저장된 시간에서 1분이 지났으므로 +1 해주면 됨)

        if cur == "S":
            if map[ny][nx] == "D":  # 고슴이가 가려는 위치가 비버네면 도착
                print(visited[y][x] + 1)
                break
            visited[ny][nx] = visited[y][x] + 1  # 비버네가 아니면 도착 시간 기록

6. 고슴이와 물 한번에 처리

  • 현재가 고슴이면 다음 좌표를 고슴이로 바꾸고
    현재가 물이면 다음 좌표를 물로 바꾼다.

  • 다음에 이어서 탐색할 수 있도록 queue에 좌표를 추가한다.

        map[ny][nx] = cur  # 다음 좌표를 고슴이 or 물로 변경
        q.append((ny, nx))  # 다음 탐색 위치 추가

7. 반복 종료 or 재반복

  • 5단계에서 고슴이가 탈출하지 못했다면 else문으로 빠진다. 이때 continue를 해서 while문을 반복하게 한다.

  • 5단계에서 고슴이가 탈출했다면 else문으로 빠지지 않는다. 이때 break를 써서 while문도 종료시킨다.

  • 고슴이가 탈출하지 못하고 while 문이 전부 종료되면 while문의 else문으로 빠진다. 이때 KAKTUS를 출력!

    else:
        continue
    break
else:
    print("KAKTUS")

끝🦔💛

전체 코드

import sys
from collections import deque
R, C = map(int, input().split())
map = [list(sys.stdin.readline().rstrip()) for _ in range(R)]

visited = [[-1] * C for _ in range(R)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

q = deque()

for y in range(R):
    for x in range(C):
        if map[y][x] == '*':  # 물 좌표를 앞에 추가
            q.appendleft((y, x))
        elif map[y][x] == 'S':  # 고슴이 좌표 추가
            q.append((y, x))
            visited[y][x] = 0  # 출발점에 시간 0 저장

while q:
    y, x = q.popleft()
    cur = map[y][x]  # 현재 위치
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]  # 다음에 갈 좌표

        if ny < 0 or ny >= R or nx < 0 or nx >= C:  # 범위 밖이면 무시
            continue
        if visited[ny][nx] != -1:  # 이미 방문한 곳 무시
            continue
        if map[ny][nx] == "*":  # 물 무시
            continue
        if map[ny][nx] == "X":  # 돌 무시
            continue
        if cur == "*" and map[ny][nx] == "D":  # 물이 비버네 가려면 무시
            continue

        if cur == "S":
            if map[ny][nx] == "D":  # 고슴이가 가려는 위치가 비버네면 도착
                print(visited[y][x] + 1)
                break
            visited[ny][nx] = visited[y][x] + 1  # 비버네가 아니면 도착 시간 기록

        map[ny][nx] = cur  # 다음 좌표를 고슴이 or 물로 변경
        q.append((ny, nx))  # 다음 탐색 위치 추가
    else:
        continue
    break
else:
    print("KAKTUS")
728x90
반응형