10026번: 적록색약

문제 풀이 아이디어

# 사용해야 하는 알고리즘 = dfs 혹은 bfs (완전탐색)
  : 다른 영역 구하는 문제와 마찬가지로 완전 탐색이 필요합니다.

# 문제 풀이 아이디어
  : 그림을 행렬로 입력을 받은 다음에
  : 방문 표시를 하면서 dfs를 돌면 됩니다.
  : 단 적록색약의 갯수를 구할 때는 행렬의 초록색을 빨간색으로 바꿉니다.

# 의사코드
  1. 입력을 받고 방문체크용 배열을 준비힙니다.
  2. 먼저 비적록색약용 dfs를 돌면서 dfs를 돈 횟수를 구합니다.
	3. 그림에서 모든 "G"를 "R"로 바꿉니다. (적록색약)
	4. 방문체크용 배열을 리셋하고 dfs를 돕니다.
  5. 결과를 출력한다.

# 시간 복잡도
  : 모든 정점을 방문하고 각 정점마다 동서남북 4번의 반복문 실행합니다.
  : 최대 O(4n**n) = O(n**2)
  : 추가로 이중 반복문 O(n**2)이 두 개 있는데 n이 최대 100이므로 안전합니다.

# ❗️주의
	: dfs를 두 종류로 나누어서 구현하려고 하면 분기문도 너무 많고 복잡합니다.
	: 이럴 때는 과감하게 input을 변형해서 더 쉬운 방법을 택합시다!

코드

// 입력 받기
let N = Int(readLine()!)!
var matrix = [[Character]]()
for _ in 0..<N {
    let line = readLine()!.map { $0 }
    matrix.append(line)
}

// 방문체크용 배열
var check = Array(repeating: Array(repeating: false, count: N), count: N)

// 동서남북 좌표 변화
let dr = [1, -1, 0, 0]
let dc = [0, 0, 1, -1]

// valid한 좌표인지 👉 color를 인자로 받아서 같은 색일 때만 true 반환
func isValid(r: Int, c: Int, color: Character) -> Bool {
    return r >= 0 && r < N && c >= 0 && c < N && matrix[r][c] == color ? true : false
}

// dfs 👉 마찬가지로 color를 인자로 받아서 같은 색만 재귀 돌도록
func dfs(r: Int, c: Int, color: Character) {
    check[r][c] = true
    
    for i in 0..<4 {
        let nr = r + dr[i]
        let nc = c + dc[i]
        if isValid(r: nr, c: nc, color: color) && !check[nr][nc] {
            dfs(r: nr, c: nc, color: color)
        }
    }

}

// 결과 저장 변수
var result1 = 0
var result2 = 0

// 비적록색약 dfs
for r in 0..<N {
    for c in 0..<N {
        if !check[r][c] {
            dfs(r: r, c: c, color: matrix[r][c])
            result1 += 1
        }
    }
}

// 적록색약이 보이는 그림으로 변형
for r in 0..<N {
    for c in 0..<N {
        if matrix[r][c] == "G" {
            matrix[r][c] = "R"
        }
    }
}

// 방문 배열 reset
check = Array(repeating: Array(repeating: false, count: N), count: N)

// 적록색약 dfs
for r in 0..<N {
    for c in 0..<N {
        if !check[r][c] {
            dfs(r: r, c: c, color: matrix[r][c])
            result2 += 1
        }
    }
}

// 결과 출력
print(result1, result2)