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

 

14923번: 미로 탈출

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이

www.acmicpc.net

기본형태의 그래프탐색 문제. 단 지팡이의 사용여부라는 조건이 붙어있다.


풀이 방법

너비 우선 탐색으로 목적지까지 그래프 탐색을 시도한다. 중복 방문을 피하기 위한 visited 배열을 3차원으로 생성.

 

visited[0][X][Y] -> 지팡이를 사용하지 않은 상태로 x,y 좌표 탐색여부,

visited[1][X][Y] -> 지팡이를 사용한 상태로 x,y, 좌표 탐색여부를 나타낸다.

 

visited 배열을 통해 좌표 탐색을 수행하여 정답을 출력하면 된다.

 

목적지에 도달하지 못하면 -1을 반환해야한다는 조건을 까먹지 말고 제출하자.


정답 코드

import Foundation
let (N,M) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0]
let (Hx,Hy) = [readLine()!.split(separator: " ").map{Int($0)!-1}].map{($0[0], $0[1])}[0]
let (Ex,Ey) = [readLine()!.split(separator: " ").map{Int($0)!-1}].map{($0[0], $0[1])}[0]
var ans = -1
var map = [[Int]]()
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: M), count: N), count: 2)
for _ in 0..<N{
let line = readLine()!.split(separator: " ").map{Int($0)!}
map.append(line)
}
func bfs(){
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
var q = [(x:Int, y:Int, wand:Bool, cnt:Int)]()
var idx = 0
q.append((Hx,Hy,false,0))
while idx < q.count{
let curr = q[idx]
if curr.x == Ex && curr.y == Ey {
ans = curr.cnt
return
}
for i in 0..<4{
let nx = curr.x + dx[i]
let ny = curr.y + dy[i]
if nx<0 || nx>=N || ny<0 || ny>=M { continue }
if curr.wand{
if map[nx][ny]==0 && !visited[1][nx][ny]{
visited[1][nx][ny] = true
q.append((nx,ny,curr.wand,curr.cnt+1))
}
}else{
if map[nx][ny]==1 && !visited[1][nx][ny]{
visited[1][nx][ny] = true
q.append((nx,ny,true,curr.cnt+1))
}else if map[nx][ny]==0 && !visited[0][nx][ny]{
visited[0][nx][ny] = true
q.append((nx,ny,curr.wand,curr.cnt+1))
}
}
}
idx += 1
}
}
bfs()
print(ans)
view raw 14923.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[3271] MEADOW  (0) 2024.05.26
[17090] 미로 탈출하기  (0) 2024.04.24
[13397] 구간 나누기 2  (0) 2024.02.28
[8983] 사냥꾼  (0) 2024.02.19
[17471] 게리멘더링  (0) 2024.02.06

+ Recent posts