[11967] 불켜기

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

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)