Hyun's_Devlog

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

처음으로 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)

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)