1867 돌멩이 제거
문제
n행 n열의 격자로 나뉜 운동장이 있다. 이 위에 k개의 돌멩이가 있는데, 하나의 돌멩이는 격자 한 칸에 정확히 들어가 있으며, 두 개 이상의 돌멩이가 한 칸에 들어가 있는 경우는 없다.
사고의 위험을 없애기 위해 이 돌멩이를 모두 제거하고 깨끗한 운동장을 만들려고 한다. 돌멩이를 제거할 때에는, 한 행이나 한 열을 따라 직선으로 달려가면서 그 행이나 열에 놓인 돌멩이를 모두 줍는 방식을 쓴다.
여러분이 할 일은 운동장의 상태가 주어졌을 때 최소 몇 번이나 달려가야 돌멩이 줍기를 끝낼 수 있는지 계산하는 것이다.
입력
첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다.
출력
첫 줄에 몇 번의 달리기를 통해 돌멩이를 주울 수 있는지 출력한다.
예제 입력 1
예제 출력 1
Solution
Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| package boj
import java.util.*
private const val MAX = 501
private var N: Int = 0
private var K: Int = 0
private var visited = BooleanArray(MAX) { false }
private var pastPath = IntArray(MAX) { 0 }
private var map = Array(MAX) {
BooleanArray(MAX) {
false
}
}
fun main() {
input()
solve()
}
private fun input() = with(Scanner(System.`in`)) {
N = nextInt()
K = nextInt()
var x: Int
var y: Int
for (i in 0 until K) {
x = nextInt()
y = nextInt()
map[x][y] = true
}
}
private fun solve() {
var result = 0
for (i in 1 .. N) {
visited = BooleanArray(MAX) { false }
if (dfs(i)) {
result++
}
}
println(result)
}
private fun dfs(index: Int): Boolean {
for (i in 1 .. N) {
if (map[index][i] && !visited[i]) {
visited[i] = true
if (pastPath[i] == 0 || dfs(pastPath[i])) {
pastPath[i] = index
return true
}
}
}
return false
}
|
Point of Thinking
- DFS로 모든 경로를 체크하면 된다.
- 힌트에 주어진 대로 운동장을
Array<BooleanArray> 타입의 2차원 배열로 표현하고, 돌멩이 여부를 true, false로 부여한다.
- 행과 열이 동일하므로, 특정 행부터 순차적으로 순회하며 dfs를 한 번 수행하고 올 때마다 카운트를 올려준다.
- 헝가리안 알고리즘으로 접근 가능한 풀이.
