문제 정보


image

풀이

그래프 이론

그래프는 정점과 그 정점들을 연결하는 간선으로 이루어진 자료구조의 일종이다

  • 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 조건에 맞는 모든 정점들을 한 번씩 방문한다
  • DFS(Depth-First-Search) 깊이 우선 탐색
  • BFS(Breath-First-Search) 너비 우선 탐색
  • 방향이 있을수도, 없을수도 있다
  • ex) 지하철 노선의 최단 경로 및 선수 과목 등

DFS

최대한 깊이 탐색한 후, 더 이상 깊이 갈 곳이 없을 경우, 옆으로 이동한다

  • 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
  • 특징
    • 모든 노드를 방문하고자 하는 경우에 선택
    • BFS보다 좀 더 간단함
    • BFS보다 검색 속도는 더 느림
    • 경로의 특징을 저장해둬야 하는 문제 혹은 검색 대상 그래프가 매우 큰 경우 사용
    • 스택 혹은 재귀함수로 구현

image
image

BFS

최대한 넓게 탐색한 후, 더 이상 갈 수 없을 때 아래로 이동한다

  • 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방식
  • 시작 노드(루트 노드)와 가까운 노드 먼저 방문하고 떨어져 있는 노드를 나중에 방문하는 순회 방식
  • 특징
    • 두 노드 사이의 최단 경로를 찾을 때 선택
    • 큐를 이용하여 구현
    • 최단 거리를 구해야 하는 문제에서 사용

DFS,BFS 시간복잡도

N : 노드의 개수 E : 간선의 개수

인접 리스트 : O(N+E) -> 더 효과적 인접 행렬 : O(N^2)

알고리즘 설계

나는 처음에 이 문제를 BFS를 사용하여 풀었다
지도의 크기가 5<=N<=25로 제한되어 있기 때문에 검색 대상 그래프가 그렇게 크지 않아 이용하였다
그래프 밖으로 인덱스가 나가는 것을 방지하기 위해서 지도를 (N+2) x (N+2) 크기로 잡아주어 -1로 지도 배열을 감싸주었다
image

그런 후, 지도 배열을 돌며 1을 만났을 때 주위에 있는 1들을 탐색하고 그 개수를 세기위해 BFS 함수 countHomeNum를 이용했다

func countHomeNum(_ x : Int, _ y : Int) {
    var queue : [(Int, Int)] = []
    var count = 0
    queue.append((x,y))
    visited[x][y] = true
    while !queue.isEmpty {
        var (x,y) = queue.remove(at: 0)
        count += 1
        for k in 0...3 {
            let nx = x + dx[k]
            let ny = y + dy[k]
            if complexArray[nx][ny] == 1 && !visited[nx][ny] {
                queue.append((nx,ny))
                visited[nx][ny] = true
            }
        }
    }
    homeCount.append(count)
 }

이 함수는 호출될 때마다 큐를 생성한 후 다음과 같은 알고리즘을 따른다

  1. 처음 탐색한 노드를 큐에 넣고 visited를 True로 한다
  2. 큐가 비어있을 때까지 while문을 반복한다
    - 큐에 있는 값을 하나 뺀다
    - count += 1
    - 동서남북에 있는 노드 중, 집이 있고, 아직 방문하지 않은 노드들을 큐에 넣는다
    - 큐에 넣은 노드들의 visited를 True로 한다
    - 다시 큐가 비어있나 확인 후 반복
  3. 한 단지를 다 탐색하면 그 집의 개수를 센 count를 homeCount에 더한다

하지만 DFS 방식의 풀이도 깔끔하고 큐를 따로 생성하지 않아 메모리도 절약할 수 있다는 장점이 있다고 생각해서 한번 풀어봤다

func DFS(_ x : Int, _ y : Int) {
    var count = 0
    if complexArray[x][y] == 1 && !visited[x][y] {
        visited[x][y] = true
        cnt += 1
        for k in 0...3 {
            DFS(x+dx[k], y+dy[k])
        }
    }
 }

단순히 방문 안하고 해당 아파트에 집이 있는 경우에 cnt += 1을 해준 후, 더 깊게 탐색하는 방식이다

전체 코드

DFS풀이
import Foundation

let N = Int(readLine()!)!
var complexArray : [[Int]] = Array(repeating: Array(repeating: -1, count: N+2), count: N+2)
var visited : [[Bool]] = Array(repeating: Array(repeating: false, count: N+2), count: N+2)
for i in 1...N {
    complexArray[i][1...N] = ArraySlice(readLine()!.map{Int(String($0))!})
}
var homeCount : [Int] = []
var cnt = 0
let dx = [1,-1,0,0]
let dy = [0,0,1,-1]

func DFS(_ x : Int, _ y : Int) {
    var count = 0
    if complexArray[x][y] == 1 && !visited[x][y] {
        visited[x][y] = true
        cnt += 1
        for k in 0...3 {
            DFS(x+dx[k], y+dy[k])
        }
    }
 }

for i in 1...N {
    for j in 1...N {
        if complexArray[i][j] == 1 && !visited[i][j]{
            cnt = 0
            DFS(i,j)
            homeCount.append(cnt)
        }
    }
}
print(homeCount.count)
homeCount.sorted(by: <).forEach{print($0)}
BFS풀이
import Foundation

let N = Int(readLine()!)!
var complexArray : [[Int]] = Array(repeating: Array(repeating: -1, count: N+2), count: N+2)
var visited : [[Bool]] = Array(repeating: Array(repeating: false, count: N+2), count: N+2)
for i in 1...N {
    complexArray[i][1...N] = ArraySlice(readLine()!.map{Int(String($0))!})
}
var homeCount : [Int] = []

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

func countHomeNum(_ x : Int, _ y : Int) {
    var queue : [(Int, Int)] = []
    var count = 0
    queue.append((x,y))
    visited[x][y] = true
    while !queue.isEmpty {
        var (x,y) = queue.remove(at: 0)
        count += 1
        for k in 0...3 {
            let nx = x + dx[k]
            let ny = y + dy[k]
            if complexArray[nx][ny] == 1 && !visited[nx][ny] {
                queue.append((nx,ny))
                visited[nx][ny] = true
            }
        }
    }
    homeCount.append(count)
 }

for i in 1...N {
    for j in 1...N {
        if complexArray[i][j] == 1 && !visited[i][j]{
            countHomeNum(i,j)
        }
    }
}
print(homeCount.count)
homeCount.sorted(by: <).forEach{print($0)}