[알고리즘/Swift] 2667 단지번호붙이기
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 2667 단지번호붙이기
- 제출 언어: Swift
- 알고리즘 분류:
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
- 깊이 우선 탐색
풀이
그래프 이론
그래프는 정점과 그 정점들을 연결하는 간선으로 이루어진 자료구조의 일종이다
- 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 조건에 맞는 모든 정점들을 한 번씩 방문한다
- DFS(Depth-First-Search) 깊이 우선 탐색
- BFS(Breath-First-Search) 너비 우선 탐색
- 방향이 있을수도, 없을수도 있다
- ex) 지하철 노선의 최단 경로 및 선수 과목 등
DFS
최대한 깊이 탐색한 후, 더 이상 깊이 갈 곳이 없을 경우, 옆으로 이동한다
- 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 특징
- 모든 노드를 방문하고자 하는 경우에 선택
- BFS보다 좀 더 간단함
- BFS보다 검색 속도는 더 느림
- 경로의 특징을 저장해둬야 하는 문제 혹은 검색 대상 그래프가 매우 큰 경우 사용
스택
혹은재귀함수
로 구현
BFS
최대한 넓게 탐색한 후, 더 이상 갈 수 없을 때 아래로 이동한다
- 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방식
- 시작 노드(루트 노드)와 가까운 노드 먼저 방문하고 떨어져 있는 노드를 나중에 방문하는 순회 방식
- 특징
- 두 노드 사이의 최단 경로를 찾을 때 선택
큐
를 이용하여 구현- 최단 거리를 구해야 하는 문제에서 사용
DFS,BFS 시간복잡도
N : 노드의 개수 E : 간선의 개수
인접 리스트 : O(N+E) -> 더 효과적 인접 행렬 : O(N^2)
알고리즘 설계
나는 처음에 이 문제를 BFS
를 사용하여 풀었다
지도의 크기가 5<=N<=25로 제한되어 있기 때문에 검색 대상 그래프가 그렇게 크지 않아 이용하였다
그래프 밖으로 인덱스가 나가는 것을 방지하기 위해서 지도를 (N+2) x (N+2) 크기로 잡아주어 -1로 지도 배열을 감싸주었다
그런 후, 지도 배열을 돌며 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)
}
이 함수는 호출될 때마다 큐를 생성한 후 다음과 같은 알고리즘을 따른다
- 처음 탐색한 노드를 큐에 넣고 visited를 True로 한다
- 큐가 비어있을 때까지 while문을 반복한다
- 큐에 있는 값을 하나 뺀다
- count += 1
- 동서남북에 있는 노드 중, 집이 있고, 아직 방문하지 않은 노드들을 큐에 넣는다
- 큐에 넣은 노드들의 visited를 True로 한다
- 다시 큐가 비어있나 확인 후 반복 - 한 단지를 다 탐색하면 그 집의 개수를 센 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을 해준 후, 더 깊게 탐색하는 방식이다
전체 코드
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)}
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)}