1달 전에오답인 상태로 방치했다가 다시 풀어본 문제다. 문제에 제시된 조건대로 구현만 하면 풀리는 문제다. 근데 집중해서 보지 않았는지 실수를 여러 번 남발해서 여러 번 시도했던 문제다. 처음엔 8가지 경우의 입력에 대해 switch 문으로 풀려했으나 코드가 너무 길어지기도 하고 코드가 길어지니 실수한 부분을 바로 찾기가 힘들었다. 설명문이 문제 자체를 이해하는 데에 실수를 유발하기 쉬운 문맥이기도 했다. 처음엔 돌과 킹이 동시에 움직이는 문제인 줄 알고 풀었고, 처음엔 둘 중 하나라도 움직일 수 없는 경우라면 둘 다 움직이지 않는 것으로 이해했었다. 결국 집중력이 부족해서 시간이 오래 걸렸던 문제다.
풀이
우선 해당 문제는 킹이 움직이는 문제다. 단, 킹이 돌이 있는 좌표로 움직이게 될 경우 돌은 킹이 움직이는 방향으로 똑같이 움직여야 한다. 추가적으로 돌이 만약 범위 밖의 좌표로 움직여야 한다면 해당 움직임은 취소. 당연히 킹도 제자리로 돌아가 다음 입력을 받아야 한다. 킹 혼자서 움직이는 경우 마찬가지로 범위 밖의 좌표로 이동해야 한다면 해당 이동은 취소다. 이번엔 문제에 대해 제대로 이해하고 각 움직임을 배열로 담아서 처리하였다.
아스키코드로 세로좌표를 표현했다. 여기서 실수했던 점은 좌표에 대한 조건을 작성하는데 65(A)부터 72(H)까지 범위를 잡아야 했지만, 아무 생각 없이 65(A)부터 90(Z)까지 범위로 잡는 실수를 했다.
탐색 종료 조건 부분에서 고생했던 문제였다. 처음에는 지도를 입력받을 때 빈칸의 개수를 세어놓고 빈칸이 0이 될 때까지 플레이어 순서대로 경로탐색을 수행하는 방법으로 시도했으나, 벽으로 둘러싸인 빈 공간의 가능성을 뒤늦게 깨달았다.
풀이
각 플레이어에게 해당하는 경로탐색용 큐 Array(repeating: [[Int]](), count: p+1)를 생성하여 앞으로 방문해야할 공간의 좌표를 담아둔다. 이후 모든 플레이어의 큐가 비어있는 상태가 될 때까지 각 플레이어 턴마다 Si번 경로탐색을 수행하면 된다. 큐의 첫 수행 좌표는 지도를 입력받을 때 큐에 담아두면 된다.
답이 생각나지 않아 점화식을 찾아보고 코드를 적어봤는데, 풀이를 이해하고서도 예외처리를 제대로 하지 못해서 오답 판정을 받았다. 결국 코드까지 찾아보고 난 후에야 풀 수 있었던 문제. 역시나 DP문제는 다양한 시점으로 생각하는 연습이 필요한 것 같다.
풀이
암호화된 문자의 길이가 n일 경우, dp:[Int] 배열은 총 n개의 배열로 dp[i]는 0번째 숫자부터 i번째 숫자까지로 만들수 있는 암호의 갯수가 담긴 배열이다. 입력된 암호문구를 순회하면서 현재 숫자가 0보다 크다면 dp[i-1]번째 경우의 수를 이어가면 되고, 추가로 직전 숫자가 0보다 크다면 현재 숫자와 합쳐 두 자리수의 대체 가능한 알파벳을 만들수 있다면 dp[i-2]번째 경우의 수를 추가로 이어가면된다. 즉 점화식은 아래와 같다.
현재 암호가 0보다 크다면, dp[i] += dp[i-1] 추가로 직전 암호가 0보다 커서 현재 암호와 이어 붙였을 시 10 이상 26 이하라면, dp[i] += dp[i-2]
점화식을 알았을 때는 간단하게 풀면 되겠다 싶었는데, 문제는 중간에 나오는 0에 대한 처리 부분이었다. 처음에는 중간에 flag 변수를 만들어 분기 처리를 하였는데, 생각보다 처리해야 할 경우가 많아서 오답처리를 받았다. 다른 유형의 문제들은 많은 문제를 풀면서 패턴에 적응해가는 과정을 통해 성장해가는 게 느껴지는 반면, DP문제는 다양한 시각에서 문제를 바라봐야 한다는 점이 여러모로 어렵게 느껴진다. 풀이는 해당 블로그에서 찾았다. 이해하기 쉽게 풀이에 대한 이미지도 있다.
처음으로 4차원 배열을 사용하여 풀어본 문제다. 입력 범위가 작아서 메모리 초과는 면할 수 있었다고 생각한다.
풀이
헛간을 표현하는 배열 map은 각 좌표에 스위치로 불을 켤 수 있는 다른 방의 좌표를 담기 위해 map[n][n] = [[a,b]...] 형태의 4차원 배열로 사용한다. 불이 켜져 있는지 확인하는 turnOn[n][n]:[[Bool]]() 배열과 방문 여부를 담는 visited[n][n] = [[Bool]]() 배열을 사용하여 좌표 탐색을 진행하면 된다.
한 가지 특이점은 예제를 보면 불을 켜게 되는 좌표가 현재 방문한 위치와 인접한 곳에 있지 않는 경우이다.([1][3]에 방문했을 때) 따라서 불을 켜게 될 때 불이 켜지게 되는 좌표의 인접 배열을 탐색하여 인접 배열중 방문했던 곳이 있는지 확인하여 기존에 방문했던 좌표에 인접한 곳이라면 다음 좌표 탐색의 큐에 넣으면 된다. 이후 기존과 동일하게 현재 위치를 기점으로 인접 배열을 확인하여 불이 켜져 있고, 방문한 적 없는 좌표를 큐에 추가로 담아 경로탐색을 수행하면 된다.
정답 코드
import Foundation
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var map = Array(repeating: Array(repeating: [[Int]](), count: n), count: n)
var turnOn = Array(repeating: Array(repeating: false, count: n), count: n)
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var ans = 0
for _ in 0..<m{
let input = readLine()!.split(separator: " ").map{Int(String($0))! - 1}
let x = input[0]
let y = input[1]
let a = input[2]
let b = input[3]
map[x][y].append([a,b])
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
func bfs(){
var q = [[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]
for button in map[x][y]{
let ax = button[0]
let by = button[1]
if !turnOn[ax][by] {
turnOn[ax][by] = true
ans += 1
for i in 0..<4{
let nx = ax+dx[i]
let ny = by+dy[i]
if nx<0 || nx>=n || ny<0 || ny>=n{ continue }
if visited[nx][ny]{
visited[ax][by] = true
q.append([ax,by])
}
}
}
}
for i in 0..<4{
let nx = x+dx[i]
let ny = y+dy[i]
if nx<0 || nx>=n || ny<0 || ny>=n{ continue }
if turnOn[nx][ny] && !visited[nx][ny]{
visited[nx][ny] = true
q.append([nx,ny])
}
}
}
}
}
turnOn[0][0] = true
visited[0][0] = true
ans = 1
bfs()
print(ans)
골드 난이도의 BFS문제를 여러 개 풀어보면서 느끼는 공통점은 기본적으로 3차원 배열을 통해 문제를 풀어야 한다는 점이다.
풀이
크게 3가지 케이스로 나누어 경로탐색을 진행해야 한다.
벽을 아직 부수지 않은 상태에서 길을 만났을 경우
벽을 아직 부수지 않은 상태에서 벽을 만났을 경우
이미 벽을 부순상태에서 길을 만났을 경우
경로를 확인하는 visited 배열은 지난번 [1600] 말이 되고픈 원숭이 문제와 같다. 지난번에는 말의 움직임을 몇 번 사용했는지를 확인했다면, 이번에는 벽을 부쉈는지(1), 부수지 않았는지(0) 두 가지만 판별하면 되므로 visited[x][y][2]의 형태로 선언하면 된다.
정답 코드
import Foundation
let nm = readLine()!.split(separator: " ").map{Int($0)!}
let n = nm[0]
let m = nm[1]
var map = Array(repeating: [Int](), count: n)
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 2), count: m), count: n)
for i in 0..<n{
map[i] = readLine()!.map{Int(String($0))!}
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
var ans = -1
func bfs(){
var q = [[0,0,0,1]]
var dq = [[Int]]()
visited[0][0][0] = true
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 wall = curr[2]
let cnt = curr[3]
if x==n-1 && y==m-1{
ans = cnt
return
}
for i in 0..<4{
let nx = x + dx[i]
let ny = y + dy[i]
if nx<0 || nx>=n || ny<0 || ny>=m {continue}
if wall==0 && map[nx][ny]==0 && !visited[nx][ny][0]{
visited[nx][ny][0] = true
q.append([nx,ny,0,cnt+1])
}
if wall==0 && map[nx][ny]==1 && !visited[nx][ny][1]{
visited[nx][ny][1] = true
q.append([nx,ny,1,cnt+1])
}
if wall==1 && map[nx][ny]==0 && !visited[nx][ny][1]{
visited[nx][ny][1] = true
q.append([nx,ny,wall,cnt+1])
}
}
}
}
}
bfs()
print(ans)
[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)
