[백준 1303] 전쟁 - 전투 (Swift)

https://www.acmicpc.net/problem/1303

 

완전탐색 (BFS)

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

 

위 처럼 가로, 세로 칸 수와 병사들의 배열이 이차원배열 형태로 주어지면, 상하좌우로 인접한 각 팀의 병사들 그룹 별로 그들의 위력(N(인접한 병사들의 수)^2)을 계산한 총합을 차례로 출력하는 문제

 

접근방법

BFS(Breadth First Search) 알고리즘으로 풀이했다. 2차원배열을 전체적으로 순회하면서 visit 배열과 queue를 가지고 W(아군)의 인접 그룹 인원수 체크, B(적군)의 인접 그룹 인원수 체크 -> 큐가 비면 그룹이 끝났다는 뜻이므로 cnt (병사수) 제곱해서 각 팀의 위력을 저장하는 변수 Strength에 더하기

 

오답노트

"가로가 N이고, 세로가 M입니다." 런타임 에러나서 범위체크했는데도 못찾아서 질문 게시판 보니까 써있었음..ㅋㅋ 문제를 잘보자

 

소스코드

import Foundation

func solution() {
    let NM:[Int] = (readLine()?.split(separator: " ").map { Int($0)! })!
    let N = NM[0]
    let M = NM[1]
    
    var map:[[Character]] = []
    for _ in 0..<M {
        let row:String = readLine()!
        map.append(Array(row))
    }
        
    // process
    let dr = [-1,1,0,0]
    let dc = [0,0,-1,1]
    
    var WStrength = 0
    var BStrength = 0
    var visit:[[Bool]] = Array<Array<Bool>>(repeating: Array<Bool>(repeating: false, count: N), count: M)
    for r in 0..<M {
        for c in 0..<N {
            if !visit[r][c] && map[r][c] == "W" {
                // 인접 그룹 인원 찾기
                var cnt = 0
                var q:[(Int, Int)] = []
                visit[r][c] = true
                q.append((r,c))
                while !q.isEmpty {
                    let now = q.removeFirst()
                    cnt += 1
                    for i in 0..<4 {
                        let nr = now.0 + dr[i]
                        let nc = now.1 + dc[i]
                        if nr >= 0 && nc >= 0 && nr < M && nc < N && map[nr][nc] == "W" && !visit[nr][nc] {
                            visit[nr][nc] = true
                            q.append((nr,nc))
                        }
                    }
                }
                WStrength += (cnt*cnt)
            }
            
            if !visit[r][c] && map[r][c] == "B" {
                // 인접 그룹 인원 찾기
                var cnt = 0
                var q:[(Int, Int)] = []
                visit[r][c] = true
                q.append((r,c))
                while !q.isEmpty {
                    let now = q.removeFirst()
                    cnt += 1
                    for i in 0..<4 {
                        let nr = now.0 + dr[i]
                        let nc = now.1 + dc[i]
                        if nr >= 0 && nc >= 0 && nr < M && nc < N && map[nr][nc] == "B" && !visit[nr][nc] {
                            visit[nr][nc] = true
                            q.append((nr,nc))
                        }
                    }
                }
                BStrength += (cnt*cnt)
            }
        }
    }
    print(WStrength, BStrength)
}

solution()