문제
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
내가 푼 풀이
- 해당 그림이 주어지면, 색의 구역의 수를 출력한다.
- 적록색약은 R,G 를 구분하지못하므로, 그래프를 탐색할 때, R과G는 같다고 판단하고 탐색한다.
- 단순히 구역의 수를 구하는 문제이므로 BFS, DFS 둘다 사용 가능하지만, DFS를 사용했다.
import Foundation
var n = Int(readLine()!)!
var arr = [[String]]()
var result = [Int]()
// dif 는 적록색약인지 판단
var dif = false
// x y 방향
var dx = [1,0,-1,0]
var dy = [0,1,0,-1]
// 그립을 배열에 입력
for i in 0..<n {
var input = Array(readLine()!).map{ String($0) }
arr.append(input)
}
// 결과 두가지 호출을 위한 result 배열
// 단순히 구역의 수를 구하기위하므로 DFS 이용
while result.count != 2 {
var needVisitQueue = [(x: Int, y: Int)]()
var count = 0
var copyArr = arr
// 정상인 사람의 구역 수 를 넣으면 색약인사람을 검사
if result.count == 1 {
dif = true
} else {
dif = false
}
// 정상인 사람의 구역의 개수 구하기
if !dif {
for i in 0..<copyArr.count {
for j in 0..<copyArr.count {
if copyArr[i][j] == "X" { continue }
needVisitQueue.append((x: j, y: i))
var check = copyArr[i][j]
while !needVisitQueue.isEmpty {
var node = needVisitQueue.removeLast()
copyArr[node.y][node.x] = "X"
for k in 0..<4 {
var cx = node.x + dx[k]
var cy = node.y + dy[k]
if (cx >= 0 && cx < n) && (cy >= 0 && cy < n) {
if copyArr[cy][cx] == check {
needVisitQueue.append((x: cx, y: cy))
}
}
}
}
count += 1
}
}
result.append(count)
} else {
// 적록색약인 사람의 구역의 개수 구하기
for i in 0..<copyArr.count {
for j in 0..<copyArr.count {
if copyArr[i][j] == "X" { continue }
needVisitQueue.append((x: j, y: i))
var check = copyArr[i][j]
while !needVisitQueue.isEmpty {
var node = needVisitQueue.removeLast()
copyArr[node.y][node.x] = "X"
for k in 0..<4 {
var cx = node.x + dx[k]
var cy = node.y + dy[k]
if (cx >= 0 && cx < n) && (cy >= 0 && cy < n) {
if check == "R" || check == "G" {
if copyArr[cy][cx] == "R" || copyArr[cy][cx] == "G" {
needVisitQueue.append((x: cx, y: cy))
}
} else if copyArr[cy][cx] == check {
needVisitQueue.append((x: cx, y: cy))
}
}
}
}
count += 1
}
}
result.append(count)
}
}
print(result.map{String($0)}.joined(separator: " "))'코딩테스트 > 백준' 카테고리의 다른 글
| BOJ-18310 안테나 Swift (0) | 2023.06.04 |
|---|---|
| BOJ-2565 전깃줄 Swift (0) | 2023.06.04 |
| BOJ-1969 DNA Swift (0) | 2023.06.02 |
| BOJ-11048 이동하기 Swift (0) | 2023.06.02 |
| BOJ-1753 최단경로 Swift (0) | 2023.06.01 |