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을 반환해야한다는 조건을 까먹지 말고 제출하자.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) |
'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 |