<백준> 적록색약(Gold 5)
[깃허브]
[백준]
https://www.acmicpc.net/problem/10026
생각보다 쉬운 문제였다.
기본적인 BFS만 알고 있으면 거기에 조건만 추가하여 구현할 수 있다.
이번에 2차원 배열을 입력받아야 했는데 이번에는 또 저번과는 다르게 CharArray로 한줄을 변환하고 그걸 배열에 집어넣는 식으로 했다.
문자 하나하나 들어가야하는 2차원배열에서는 앞으로 이 방식을 사용해야겠다.
그리고 이제 함수들을 만들었다.
2차원 배열을 돌면서 시작점이 될 수 있는지 확인하고 bfs를 시작시키는 함수와 bfs를 하면서 구역을 먹는 함수 2개를 만들었다.
첫번째 함수에서는 bfs가 끝날 때 count를 1씩 더해줬다.
한 구역이 다 끝난 거기 때문이다.
두번째 함수에서는 시작점의 색깔을 저장해놨다.
그리고 그걸 이동하는 칸의 색깔과 비교하며 같은 구역에 포함될 수 있는지 체크했다.
이 문제에서 조금 신경쓴 것은 bfs 함수를 하나만 만든 것이다.
케이스 2가지를 구해야하지만 다른 점은 빨강,초록을 하나로 보는지 둘로 보는지였기 때문에 조건문만 잘 처리한다면 하나로 된다는 생각이 들었다.
이전에 자바로 풀었던 걸 다 풀고 나서 보니까 bfs 함수를 두개 만들어서 했더라
하지만 이번에는 한개로 해결했다.
type 변수를 넘겨받아 어떤 케이스인지 체크하고 해당 케이스에 맞는 조건문을 돌도록 했다.
이 부분에서 빨강, 초록을 하나로 볼때, 빨강에서 파랑이 안 되는건 추가했는데 초록에서 파랑이 안 되는 건 추가하지 않아서 한번 틀렸었다.
반례를 좀 넣다보니 확인이 되어서 금방 통과했다.
해당 방법으로 작성한 코드는 다음과 같다.
var n: Int = 0
lateinit var painting: Array<CharArray>
val dy = listOf(0, 1, 0, -1)
val dx = listOf(1, 0, -1, 0)
fun main() = with(System.`in`.bufferedReader()) {
n = readln().toInt()
painting = Array(n) { charArrayOf() }
for (i in 0 until n) {
painting[i] = readln().toCharArray()
}
print("${getArea(1)} ${getArea(2)}" )
}
fun getArea(type: Int): Int {
val visited = Array(n) { Array(n) { false } }
var count = 0
for (i in 0 until n) {
for (j in 0 until n) {
if (visited[i][j].not()) {
bfs(visited, i, j, type)
count++
}
}
}
return count
}
fun bfs(visited: Array<Array<Boolean>>, r: Int, c: Int, type: Int) {
val q = ArrayDeque<Pair<Int, Int>>()
q.add(Pair(r, c))
visited[r][c] = true
val color = painting[r][c]
while (q.isNotEmpty()) {
val cur = q.removeFirst()
for (i in 0 until 4) {
val newRow = cur.first + dy[i]
val newCol = cur.second + dx[i]
if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= n) continue
if (visited[newRow][newCol]) continue
if (type == 1) {
if (painting[newRow][newCol] != color) continue
} else {
if (color == 'R' && painting[newRow][newCol] == 'B' ||
color == 'G' && painting[newRow][newCol] == 'B' ||
color == 'B' && painting[newRow][newCol] != color) continue
}
q.add(Pair(newRow, newCol))
visited[newRow][newCol] = true
}
}
}