Hyun's_Devlog

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

bfs를 두 번 사용해서 풀었다. 중간에 변수명이 겹친걸 못 알아채서 쓸데없는 부분에서 시간을 오래 끌었던 문제였다. 조금 더 집중해서 풀이를 생각하는 연습이 필요한 것 같다.

풀이

입력으로 육지와 바다에 대한 구분이 들어온다. 우선 기본적인 bfs를 통해 각 컴포넌트를 구분 짓는 작업을 해준다. 그 이후 한번 더 bfs를 통해 짧은 다리를 찾으면 되는데, 경로탐색의 조건은 다음과 같이 정의했다.

• 상하좌우를 확인하여, 바다인 경우만 큐에 넣고 탐색
• 바다가 아닌 곳이라면 경로탐색 시작 컴포넌트와 다른 컴포넌트인지 확인하여 다른 곳이라면 다리 길이를 갱신 후 종료
• 경로 탐색 중 현재 갱신된 다리 길이보다 길다면 종료

정답 코드

주석 처리된 부분은 알맞게 풀고 있는지 확인하려 적은 코드이다.

import Foundation

let n = Int(readLine()!)!
var map = Array(repeating: [Int](), count: n)
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var land = Array(repeating: Array(repeating: 0, count: n), count: n)

for i in 0..<n{
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    map[i] = input
}

let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
func numbering(x:Int, y:Int, landNumber:Int){
    var q = [[x,y]]
    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 i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=n || ny<0 || ny>=n || map[nx][ny]==0{ continue }
                if !visited[nx][ny]{
                    visited[nx][ny] = true
                    land[nx][ny] = landNumber
                    q.append([nx,ny])
                }
            }
        }
    }
}

var number = 1
for i in 0..<n{
    for k in 0..<n{
        if !visited[i][k] && map[i][k] != 0{
            visited[i][k] = true
            land[i][k] = number
            numbering(x: i, y: k, landNumber: number)
            number += 1
        }
    }
}
//for l in land{ print(l) }
var ans = n*n
var check = visited
func bridge(ix:Int,ky:Int){
    visited = Array(repeating: Array(repeating: false, count: n), count: n)
    var q = [[ix,ky,0]]
    var dq = [[Int]]()
    let landNumber = land[ix][ky]
    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]
            if cnt > ans{
                return
            }
            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 !visited[nx][ny] && land[nx][ny]==0{
                    visited[nx][ny] = true
                    q.append([nx,ny,cnt+1])
                }
                if !visited[nx][ny] && land[nx][ny]>0 && land[nx][ny] != landNumber{
//                    print("land[\(ix)][\(ky)]:\(landNumber) -> land[\(nx)][\(ny)]:\(land[nx][ny]), cnt:\(cnt)")
                    ans = min(ans, cnt)
                    return
                }
            }
        }
    }
}

visited = Array(repeating: Array(repeating: false, count: n), count: n)
for x in 0..<n{
    for y in 0..<n{
        if land[x][y]>0{
            bridge(ix: x, ky: y)
        }
    }
}
print(ans)

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

숨바꼭질 시리즈의 문제다. 선행 문제와 같은 방식으로 풀어보려 했으나 이번에는 동생이 움직인다는 조건이 붙어서 오답을 받았다. 풀이를 찾아보고 풀 수 있었던 문제였다. 

풀이

기존의 숨바꼭질 문제에서는 visited[n] 방문 배열을 "거리 n에 도달하는 데에 걸리는 시간"으로 설정하여 경로탐색으로 더 짧은 시간으로 갱신시켜 답을 구했다면 이번에는 동생이 이동한다는 조건 때문에 다른 방식으로 접근해야 한다. 수빈이가 동생이 도착할 장소에 미리 도착하여 한 칸 전진, 한 칸 후진 즉 2초를 소비하여 해당 자리에서 대기하는 것이 가능하다.

그렇다면 구분해야할것은 해당 시간과 위치에 홀수 초에 도착하는지 짝수 초에 도착하는지를 확인하여 해당 시간을 반환하면 된다. 따라서 방문 배열은 visited[t][k]:[[Bool]] 2차원 배열로 설정하고 t%2초에 k번째 위치에 방문했는지를 갱신하여 경로탐색을 해주면 된다. 시간이 갱신될 때마다 동생의 위치 k번째 배열 값이 참이라면 해당 시간을 반환하면 된다. 역시 설명보단 코드가 이해하기 더 쉬울 것이다.

정답 코드

import Foundation

let nk = readLine()!.split(separator: " ").map{Int($0)!}
let n = nk[0]
var k = nk[1]
var ans = -1

var map = Array(repeating: Array(repeating: false, count: 2), count: 500001)
map[n][0] = true
var time = 0

func bfs(){
    var q = [n]
    var dq = [Int]()
    while !q.isEmpty{
        k += time
        dq = q.reversed()
        q.removeAll()
        if k<0 || k>500000{return}
        if map[k][time%2]{
            ans = time
            return
        }
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let next = [curr-1,curr+1,curr*2]
            
            for next in next{
                if next<0 || next>=500001{continue}
                if !map[next][(time+1)%2]{
                    map[next][(time+1)%2] = true
                    q.append(next)
                }
            }
        }
        time += 1
    }
}
bfs()
print(ans)