[백준] (Swift) 1941번 - 소문난 칠공주 (골드3) (DFS)

이번에도 막상 구현은 어렵지 않은 DFS 관련 문제였지만, 생각하는데 조금 많은 길을 가야했다. 그래도 DFS, BFS에 대한 감을 조금씩 잡아가고 있는 것 같아서 너무 기쁘다!

 

⚫️ 문제

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

1941번: 소문난 칠공주

 

⚫️ 생각의 흐름

1️⃣ 첫번째 생각

일단 연결된 7명의 친구들을 찾아야하는 것이 우선인 것 같았다. 그래서 DFS를 이용해서 7명의 친구들을 탐색하면서, 그 친구들이 S인지 Y인지 판단하고, Y가 4명을 넘어가는 순간 해당 탐색을 종료해주는 백트래킹 방식을 사용하고자 했다. 

그래서 위 그림을 조금 해석해보자면, (0,0)의 위치부터 DFS를 이용해서 사방탐색을 진행하고, 방문처리를 해주면서 이동하고 S와 Y의 갯수를 판단해주고 return될때 방문처리를 false처리해주면서 다시 다음 탐색을 할 수 있도록 했다.

❌ 이 풀이로 진행하지 못했던 이유

곰곰히 생각해보니까, 학생들은 전부! 인접해 있으면된다. 아래 두 경우를 살펴보자.

DFS는 지금 탐색중인 노드로부터 상하좌우를 살피고 이동한다. 그리고 이동하면 그 위치에서 다시 상하좌우를 살핀다. 우 방향으로 갔다가 좌 방향으로 다시 되돌아가도 되지만, 이미 한번 거쳐온 노드는 방문처리가 되어있기 때문에 다시 돌아갈 수없다. 그래서 DFS는 결국, 한 방향, 연결된 하나의 화살표 방향으로만 이동할 수 있다. (왔다가 되돌아갈 수 없다.)

왔다가 되돌아가는 DFS로도 구현이 가능하긴 하지만, 이 문제에서는 어차피 한번 count한 학생은 또 count되지 않아야하기 때문에 visited가 필요하다. 그래서 되돌아가게 구현이 어렵다는 판단이었다.

2️⃣ 두번째 생각

두번째로 생각한 것은, '완전탐색'을 먼저 생각해냈다. 왜냐하면, 문제를 보면, 항상 입력값은 5x5 로 주어진다. 그럼, 여기서 7명을 골라내는데에는 max값이 정해져있다. 25개중 7개를 고르는 (25C7, combination) 만큼만 탐색해주면 된다.

완전탐색을 하기 위해서 가장 중요한, 조건을 살펴보고 시간복잡도가 어떻게 될지 고민해봤다. 일단,, 25개에서 7개를 뽑아내는 경우의 수는 48만개 정도 된다. (계산기 땡큐) 그리고 백준에서 주어진 시간은 2초. (파이썬 기준으로 2초면 2억회 돌아간다고 생각하면 되니까, 일단 48만회 돌아가는 것은 시간적으로 여유가 있을 것 같았다. 그리고 지금 내 뇌피셜상, 100만 이하는 무조건 완탐을 돌려도 상관이 없다고 판단하고 있다.)

그래서 여기 노란색 형광팬 처럼 생각해냈다. 저렇게 구현해보자....

🔖 48만개 먼저 만들어주자 

가장 먼저 combination을 구현해주어야했다. 스위프트는 내장되어있는 combination 메서드가 없기 때문에,,, 예전부터 살짝! 재귀로 구현하는 방법에 대해서 익혀두고 있었다. (지금도 구현하는데 조금 참고했ㄷ.ㅏ 헤ㅔ헤  참고글 - https://inuplace.tistory.com/1189

어차피 25개의 배열이 주어지니까, 0부터 24까지의 숫자를 통해서 배열을 만들었다. 숫자만 있어도 row와 column 숫자를 구할 수 있기 때문이었다! 복잡하게 (0,0) (0,1),,, 이렇게 좌표값을 가지고 조합을 만들지 않았다.

🔖 그리고 S의 개수를 판단해주는 함수 생각

그다음 S의 개수를 판단해주는 함수를 만들었다. 이 함수는, combination으로부터 도출된 48만개의 배열중 하나를 받아와서, 그 배열 내부에서 각 위치에 S와 Y가 몇개인지 세어주었다. S가 4개가 넘어가는 순간 true를 리턴해주고 Y가 4개가 넘어가는 순간 False를 리턴해주도록 만들면 된다고 판단했다.

🔖 7개가 연결되어있는지 확인

7개가 연결되어있는지 확인하는 방법을 생각하는데 시간이 좀 걸렸다. 내가 조합을 만든 방법이 0부터 24까지의 숫자로 만들었으니까, 나머지가 같거나 몫이 같은 경우를 묶어서 같은지 판단하고 연결 여부를 판단하고자 했다. 근데,,, 이렇게 잘 안됐다. 그래서 다른방법을 생각해냈다.

다른 방법은 BFS를 통해서 인접노드를 찾아주는 방식이었다. BFS가 최단경로를 찾아준다고 알려져있긴 하지만, 사실 생각해보면, BFS가 동작하는 방식을 떠올려보면, 현재 탐색중인 노드랑 인접한 애들을 전부 queue에 넣어주고, queue를 소진할때까지 탐색을 진행한다. BFS에 넣어줄 arr는 길이 7짜리 배열이고, 7개 모두가 인접되어있어야하니까, 결국 도출될 때 7개 모두 visited 처리가 되어있으면 모두 방문했다는 뜻, 즉 모두 인접해서 queue에 한번 들어갔다가 나왓다는 뜻으로 해석할 수 있다!

이 모든 것을 차근차근 구현하면,, 정답을 구할 수 있다. 헤헤 재밋다 이런문제 너무!

⚫️ 정답코드

import Foundation

var location = [[String]]()
for _ in 0..<5 {
    location.append(readLine()!.map{ String($0) })
}

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

func solution() {
    // 48만개 조합 생성
    let combiArr = combi(arr: Array(stride(from: 0, through: 24, by: 1)), n: 7)
    var answer = 0

    for c in combiArr {
        if checkScnt(arr: c) {
            if isConnection(arr: c) {
                answer += 1
            }
        }
    }

    print(answer)
}

func checkScnt(arr: [Int]) -> Bool {
    // 다솜(S)가 4명 이상이면 true
    var sCnt = 0
    var yCnt = 0

    for i in 0..<7 {
        if sCnt >= 4 {
            return true
        } else if yCnt >= 4 {
            return false
        }

        let x = arr[i] / 5
        let y = arr[i] % 5
        if location[x][y] == "S" {
            sCnt += 1
        } else if location[x][y] == "Y" {
            yCnt += 1
        }
    }

    if sCnt >= 4 {
        return true
    }

    return false
}

func isConnection(arr: [Int]) -> Bool {
    var check = Array(repeating: false, count: 7) // arr에 맞춰서 인덱스로 구별
    var queue = [(Int, Int)]()

    func bfs(index: Int) {
        queue.append((arr[index] / 5, arr[index] % 5))
        check[index] = true

        while !queue.isEmpty {
            let temp = queue.removeFirst()
            let x = temp.0
            let y = temp.1

            for i in 0..<4 {
                let nx = x + dx[i]
                let ny = y + dy[i]

                if nx < 0 || ny < 0 || nx >= 5 || ny >= 5 {
                    continue
                }

                if arr.contains((nx * 5) + ny), !check[arr.firstIndex(of: (nx * 5) + ny)!] {
                    check[arr.firstIndex(of: (nx * 5) + ny)!] = true
                    queue.append((nx, ny))
                }
            }
        }
    }

    bfs(index: 0)

    if check.filter({ $0 == true }).count == 7 {
        return true
    }

    return false
}

func combi(arr: [Int], n: Int) -> [[Int]] {
    var combiArr = [[Int]]()

    func dfs(index: Int, now: [Int]) {
        if now.count == n {
            combiArr.append(now)
            return
        }

        for i in index..<arr.count {
            dfs(index: i + 1, now: now + [arr[i]])
        }
    }

    dfs(index: 0, now: [])
    return combiArr
}

solution()

 

 

이 문제는 문제 속에 힌트가 숨겨져있던게 특징이었다. 바로 입력값이 항상 25개라는 것을 파악하는 것!!!