[파이썬, 스위프트][백준 17836][💛골드 5] 공주님을 구해라! (BFS)

🧞‍♂️ 난이도

💛 골드 5

🧞‍♂️ 문제

https://www.acmicpc.net/problem/17836

🧞‍♂️ 풀이 방법

1. 그냥 일반적인 BFS 로 최단경로 구한다.
2. 그람(2) 를 만나면 다이렉트로 N-1, M-1 까지의 거리를 구해놓는다.
3. 최단경로랑 그람거리의 최솟값이 정답이다.
   • 단 T 보다 작으면 ‘Fail’출력한다.

🧞‍♂️ 파이썬 코드

import sys, collections
input = sys.stdin.readline
N, M, T = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

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

def bfs():
    global sword
    visited = [[0] * M for _ in range(N)]
    visited[0][0] = 1
    q = collections.deque()
    q.append((0, 0, 0)) #x, y, time
    while q:
        cur_x, cur_y, time = q.popleft()
        for i in range(4):
            nx, ny = cur_x + dx[i], cur_y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0 and board[nx][ny] != 1:
                if nx == N-1 and ny == M-1:
                    return time + 1
                if board[nx][ny] == 2:
                    sword = abs(N-1-nx) + abs(M-1-ny) + time + 1
                visited[nx][ny] = 1
                q.append((nx, ny, time + 1))
    return float('inf')

sword = float('inf')
answer = min(bfs(), sword)
print(answer if answer <= T else "Fail")

🧞‍♂️ 스위프트 코드

import Foundation

func getTime(_ x: Int, _ y: Int, _ nx: Int, _ ny: Int) -> Int {
    return abs(nx - x) + abs(ny - y)
}

func solution(_ N: Int, _ M: Int, _ T: Int, _ board: [[Int]]) -> Int {
    let dx = [1, -1, 0, 0]
    let dy = [0, 0, -1, 1]
    var visited = Array(repeating: Array(repeating: false, count: M), count: N)
    var q: [(Int, Int, Int)] = [(0, 0, 0)]
    var swordTime = Int.max
    var swordlessTime = Int.max
    var nx = 0
    var ny = 0
    var counter = 0
    visited[0][0] = true

    while counter < q.count {
        let (x, y, currentTime) = q[counter]

        for i in 0..<4 {
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 > nx || N <= nx || 0 > ny || M <= ny || visited[nx][ny] || board[nx][ny] == 1 {
                continue
            }
            if nx == N-1 && ny == M-1 {
                swordlessTime = min(swordlessTime, currentTime + 1)
                break
            }
            if board[nx][ny] == 2 {
                swordTime = currentTime + 1 + getTime(nx, ny, N-1, M-1)
            }
            visited[nx][ny] = true
            q.append((nx, ny, currentTime+1))
        }
        counter += 1
    }
    return min(swordlessTime, swordTime)
}

let NMT = readLine()!.split(separator: " ").compactMap { Int($0) }
let N = NMT[0]
let M = NMT[1]
let T = NMT[2]
var board: [[Int]] = []

for _ in 0..<N {
    let col = readLine()!.split(separator: " ").compactMap { Int($0) }

    board.append(col)
}

let time = solution(N, M, T, board)

print(time <= T ? time : "Fail")

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기