[백준 14466] 소가 길을 건너간 이유 6

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

✍️ 첫번째 접근

문제를 봤을 때, 이해하는데 시간이 오래 걸렸다. 내가 독해력이 부족한 것인가 생각까지 했다.
예시에 대한 그림은 아래와 같다.



따라서, 예제에서의 입력으로 인한 출력으로 2가 나오는 것이다.
필자는 각 좌표를 쉽게 사용하기 위해 구조체를 선언하였고 목초지를 잇는 길에 대한 각각의 좌표를 Dictionary 타입으로 저장하였다. 예를 들어 입력으로 3 3 3 2과 3 3 2 3이 들어왔다면 [3,3] key에 [[3,2], [2,3]]을 value로 저장한다.
소의 좌표를 저장한 배열을 2중 for문 돌려 길을 건널 수 있는지 없는지를 판단하여 길을 건너야지만 만날 수 있는 쌍의 개수를 출력하려 했다.
하지만 틀리게 되었는데 길이 있는 좌표에 소가 길을 건널 수 있다는 의미가 무조건 길을 건너야지만 건널 수 있다는 의미가 아니기 때문이다. 즉, 논리가 부족하였다.

import Foundation

struct Point: Hashable {
    var x: Int
    var y: Int
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var arr: [Point: Set<Point>] = [:]
var cows: [Point] = []
var cnt = 0
for _ in 0..<input[2] {
    let point = readLine()!.split(separator: " ").map { Int(String($0))! }
    let x1 = point[0], y1 = point[1], x2 = point[2], y2 = point[3]
    if arr[Point(x: x1, y: y1)] == nil {
        arr.updateValue([Point(x: x1, y: y1)], forKey: Point(x: x1, y: y1))
        arr[Point(x: x1, y: y1)]?.insert(Point(x: x2, y: y2))
    }
    else {
        arr[Point(x: x1, y: y1)]?.insert(Point(x: x2, y: y2))
    }
    if arr[Point(x: x2, y: y2)] == nil {
        arr.updateValue([Point(x: x2, y: y2)], forKey: Point(x: x2, y: y2))
        arr[Point(x: x2, y: y2)]?.insert(Point(x: x1, y: y1))
    }
    else {
        arr[Point(x: x2, y: y2)]?.insert(Point(x: x1, y: y1))
    }
}
for _ in 0..<input[1] {
    let point = readLine()!.split(separator: " ").map { Int(String($0))! }
    cows.append(Point(x: point[0], y: point[1]))
}
for i in cows {
    for j in cows {
        if arr[i] == nil || arr[j] == nil {
            cnt += 1
            continue
        }
        if !arr[i]!.contains(j) {
            cnt += 1
        }
    }
}
print(cnt)

✍️ 두번째 접근

소의 좌표를 저장한 배열을 2중 for문 돌 때, BFS를 돌려 A라는 소에서 출발하였을 때 길을 사용하지 않고 B라는 소를 만날 수 없다면 즉, A, B 소의 한쌍은 길을 건너야하지만 만날 수 있으면 그 한쌍이 우리가 원하는 한쌍이라고 판단하였다.
각 쌍에 대하여 반복문을 돌 때, visited를 초기화해줘야함을 잊어서는 안된다.
이렇게 구현하여 문제를 해결하였다.

import Foundation

let dx = [1,0,-1,0]
let dy = [0,1,0,-1]

func BFS(_ i: Int, _ j: Int) {
    var queue: [Point] = []
    queue.append(Point(x: i, y: j))
    visited[i][j] = true
    while !queue.isEmpty {
        let cur = queue.first!
        queue.removeFirst()
        for dir in 0..<4 {
            let nx = cur.x + dx[dir]
            let ny = cur.y + dy[dir]
            if arr[Point(x: cur.x, y: cur.y)] != nil && arr[Point(x: cur.x, y: cur.y)]!.contains(Point(x: nx, y: ny)) {
                continue
            }
            if nx <= 0 || nx > input[0] || ny <= 0 || ny > input[0] {
                continue
            }
            if visited[nx][ny] == true {
                continue
            }
            queue.append(Point(x: nx, y: ny))
            visited[nx][ny] = true
        }
    }
}

struct Point: Hashable {
    var x: Int
    var y: Int
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var arr: [Point: Set<Point>] = [:]
var cows: [Point] = []
var cnt = 0
for _ in 0..<input[2] {
    let point = readLine()!.split(separator: " ").map { Int(String($0))! }
    let x1 = point[0], y1 = point[1], x2 = point[2], y2 = point[3]
    if arr[Point(x: x1, y: y1)] == nil {
        arr.updateValue([Point(x: x2, y: y2)], forKey: Point(x: x1, y: y1))
    }
    else {
        arr[Point(x: x1, y: y1)]?.insert(Point(x: x2, y: y2))
    }
    if arr[Point(x: x2, y: y2)] == nil {
        arr.updateValue([Point(x: x1, y: y1)], forKey: Point(x: x2, y: y2))
    }
    else {
        arr[Point(x: x2, y: y2)]?.insert(Point(x: x1, y: y1))
    }
}
for _ in 0..<input[1] {
    let point = readLine()!.split(separator: " ").map { Int(String($0))! }
    cows.append(Point(x: point[0], y: point[1]))
}

var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: input[0]+1), count: input[0]+1)
for i in 0..<cows.count {
    visited = Array(repeating: Array(repeating: false, count: input[0]+1), count: input[0]+1)
    BFS(cows[i].x,cows[i].y)
    for j in i+1..<cows.count {
        if visited[cows[j].x][cows[j].y] == false {
            cnt += 1
        }
    }
}
print(cnt)