https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
[4179] 불! 문제보다는 체감상 쉽게 다가왔다. 불! 문제에서 너무 고생해서 그랬나 보다. 물론 한 번에 통과하진 못했고, 결국 답을 찾아보았지만 조금만 더 깊이 생각했으면 답에 도달하지 않았을까 싶다.
풀이
늘 bfs문제를 풀듯이, 상하좌우 좌표의 확인과 말의 이동방식의 좌표 확인 과정을 추가해서 경로를 탐색하면 된다. 중요한 점은 말의 움직임은 k번까지만 가능하고, 말의 움직임과 원숭이의 움직임에 대해 순서가 뒤섞여서 움직일 수 있다는 점이다. 해당 부분에 대한 처리가 어설퍼서 처음에는 오답 판정을 받았다.
큐에는 다음 좌표와 말의 움직임을 몇번 사용하였는지, 그리고 지금까지의 총 이동 횟수를 담아 확인했다. 이후 방문 여부를 확인하는 visited 배열을 3차원으로 생성하는 것이 핵심이다. visited[k][x][y] 배열을 통해 k번째 말의 움직임과 일반적인 움직임의 조합으로 경로를 탐색한다. 각 k번째 visited 배열에는 해당 횟수에서 이동 가능한 말의 움직임 + 원숭이의 움직임에 대한 방문 여부를 확인하고 경로탐색을 수행하면 된다. 설명보단 코드로 보는 것이 이해하기 더 쉬울 것이다.
오답 코드
해당 코드에서는 말의 움직임에 대해 깊이 고민하지 않고, 일반적인 visited배열을 사용하여 오답 판정을 받았다.
import Foundation
let k = Int(readLine()!)!
let wh = readLine()!.split(separator: " ").map{Int($0)!}
let w = wh[0]
let h = wh[1]
var ans = -1
var length = 0
var map = Array(repeating: Array(repeating: 0, count: w), count: h)
var visited = Array(repeating: Array(repeating: false, count: w), count: h)
for x in 0..<h{
let land = readLine()!.split(separator: " ").map{Int($0)!}
for y in 0..<w{
map[x][y] = land[y]
}
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
let hx = [-1,-2,-2,-1,1,2,2,1]
let hy = [-2,-1,1,2,2,1,-1,-2]
func bfs(){
var q = [[0,0,k,length]]
var dq = [[Int]]()
while !q.isEmpty{
dq = q.reversed()
q.removeAll()
for _ in 0..<dq.count{
let curr = dq.removeLast()
let x = curr[0]
let y = curr[1]
let cnt = curr[2]
let len = curr[3]
if x==h-1 && y==w-1{
ans = len
return
}
if cnt>0{
for i in 0..<8{
let nx = x+hx[i]
let ny = y+hy[i]
if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
if !visited[nx][ny]{
visited[nx][ny] = true
q.append([nx,ny,cnt-1,len+1])
}
}
}
for i in 0..<4{
let nx = x+dx[i]
let ny = y+dy[i]
if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
if !visited[nx][ny]{
visited[nx][ny] = true
q.append([nx,ny,cnt,len+1])
}
}
}
}
}
visited[0][0] = true
bfs()
print(ans)
정답 코드
import Foundation
let k = Int(readLine()!)!
let wh = readLine()!.split(separator: " ").map{Int($0)!}
let w = wh[0]
let h = wh[1]
var ans = -1
var map = Array(repeating: Array(repeating: 0, count: w), count: h)
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 31), count: w), count: h)
for x in 0..<h{
let land = readLine()!.split(separator: " ").map{Int($0)!}
for y in 0..<w{
map[x][y] = land[y]
}
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
let hx = [-1,-2,-2,-1,1,2,2,1]
let hy = [-2,-1,1,2,2,1,-1,-2]
func bfs(){
var q = [[0,0,0,0]]
var dq = [[Int]]()
while !q.isEmpty{
dq = q.reversed()
q.removeAll()
for _ in 0..<dq.count{
let curr = dq.removeLast()
let x = curr[0]
let y = curr[1]
let cnt = curr[2]
let length = curr[3]
if x==h-1 && y==w-1{
ans = length
return
}
if cnt<k{
for i in 0..<8{
let nx = x+hx[i]
let ny = y+hy[i]
if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
if !visited[nx][ny][cnt+1]{
visited[nx][ny][cnt+1] = true
q.append([nx,ny,cnt+1,length+1])
}
}
}
for i in 0..<4{
let nx = x+dx[i]
let ny = y+dy[i]
if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
if !visited[nx][ny][cnt]{
visited[nx][ny][cnt] = true
q.append([nx,ny,cnt,length+1])
}
}
}
}
}
visited[0][0][0] = true
bfs()
print(ans)
'Problem Solving > BOJ' 카테고리의 다른 글
| [17071] 숨바꼭질 5 (0) | 2022.10.12 |
|---|---|
| [2206] 벽 부수고 이동하기 (0) | 2022.10.06 |
| [4179] 불! (0) | 2022.09.29 |
| [2294] 동전 2 (0) | 2022.09.22 |
| [15988] 1, 2, 3 더하기 3 (0) | 2022.09.20 |
