[백준 18428] 감시 피하기 (Swift)

문제 :

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

18428번: 감시 피하기

 

1. 문제 이해하기

• NxN 크기의 그래프가 있습니다.
• 각 칸에는 선생님(T), 학생(S), 복도(X)가 존재하고 복도에 장애물을 세워서 선생님의 감시를 피하고자 합니다.
• 각 선생님은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행하고 아무리 멀리 있더라도 장애물로 막히기 전까지 학생들을 모두 감시할 수 있습니다.
• 학생들은 복도의 빈칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치해야 한다. 결과적으로 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지 판별하고자 합니다.

 

2. 문제 풀이 생각하기

1. 처음에는 예시를 봤을 때 선생님이 학생을 감시할 수 있는 위치라면, 선생님 혹은 학생 바로 앞에 장애물을 설치하면 된다고 생각했습니다. 하지만 일방적으로 선생님 앞, 또는 학생 앞에만 장애물을 설치하면 막히지 않는 경우의 수가 있다는 것을 알고 모든 경우의 수를 봐야 한다고 판단했습니다.
2. 모든 경우의 수는 모든 복도 칸 중에서 3개를 뽑는 경우의 수(조합)이고 그 조합들 중에서 한 선생님이라도 학생을 감시할 수 있다면 해당 경우를 배제하는 백트래킹 방식을 이용했습니다.
3. dfs() 함수, 해당 조합에서 선생님이 학생을 감시할 수 있는지 없는지 판별하는 isFind() 함수를 정의합니다.
4. 먼저 입력을 받을 때, 선생님의 위치와 빈 복도를 저장하는 각각 배열 teacherLocations, roads에 저장합니다.
5. dfs() 함수에서 모든 복도를 방문하면서 장애물(B)을 설치하고 다음 복도 위치의 인덱스와 장애물 설치 개수를 매개변수로 깊이 우선 탐색을 진행합니다.
6. 깊이 우선 탐색이 풀릴 때는 기존에 복도에 세웠던 장애물(B)을 다시 복도(X)로 바꿉니다. (이전 경우의 수 기록을 reset 하기 위함)
7. 장애물을 세운 개수가 3개라면, isFind() 함수에서 모든 선생님의 위치에서 학생을 감시할 수 있으면 true 감시할 수 없으면 false
8. 만약 감시할 수 없는 경우를 찾았다면 ans = "YES"
9. 5 ~ 8 반복

 

문제의 첫 번째 예제 입력으로 설명해보겠습니다.

 

3. 차근차근 구현하기

import Foundation

let n = Int(readLine()!)!
var graph = Array(repeating: Array(repeating: "", count: n), count: n)
var teacherLocations = [[Int]]() // 모든 선생님 위치 좌표
var roads = [[Int]]() // 모든 빈 복도 좌표
var cnt = 3
let d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
var ans = "NO"

for i in 0..<n {
    let line = readLine()!.components(separatedBy: " ").map { String($0) }
    for j in 0..<n {
        graph[i][j] = line[j]
        if line[j] == "T" {
            teacherLocations.append([i, j])
        }
        else if line[j] == "X" {
            roads.append([i, j])
        }
    }
}

func boundary(_ i: Int, _ j: Int) -> Bool {
    return 0 <= i && i < n && 0 <= j && j < n
}

// 각 선생님 위치에서 학생을 한 명이라도 감시할 수 있는지 판별
func isFind() -> Bool {
    for teacherLocation in teacherLocations {
        for k in d {
            var ni = teacherLocation[0]
            var nj = teacherLocation[1]
            
            while true {
                ni += k[0]
                nj += k[1]
                if !boundary(ni, nj) || graph[ni][nj] == "B" {
                    break
                }
                else if graph[ni][nj] == "S" {
                    return true
                }
            }
        }
    }
    return false
}

// index를 인덱스로 받는 이유 -> 순열 방지
func dfs(_ index:Int, _ cnt: Int) {
    if cnt == 3 {
    	// 모든 선생님이 한 명의 학생도 감시할 수 없는 경우 ans = "Yes"
        if !isFind() {
            ans = "YES"
        }
        return
    }
    
    for i in index..<roads.count {
        let ni = roads[i][0]
        let nj = roads[i][1]
        graph[ni][nj] = "B"
        dfs(i + 1, cnt + 1)
        graph[ni][nj] = "X"
    }
}

dfs(0, 0)
print(ans)

 

4. 피드백

• 실버 5 치고는 생각보다 생각할 게 많았던 것 같다. 백트래킹 문제를 더 많이 풀어봐야겠다.