[백준 1303] [Kotlin] 전쟁 - 전투

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

1303번: 전쟁 - 전투

 

난이도 : 실버 1
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

---

1. 설명

 

전형적인 그래프 탐색 문제입니다.

 

그래프 탐색 알고리즘은 DFS(깊이 우선 탐색)과 BFS(넓이 우선 탐색)으로 풀 수 있는 문제입니다.

 

DFS와 BFS중 어느 걸 사용하던 무방하지만, 저는 DFS를 사용하도록 하겠습니다.

 

---

2. 소스코드

      

      

      

    
    

      <code />
    
var n = 0
var m = 0
var cnt = 0
lateinit var map: Array<Array<String>>

      

      

      

    
    

      <code />
    
val nm = readLine()!!.split(" ")
var wPower = 0.0
var bPower = 0.0

n = nm[1].toInt()
m = nm[0].toInt()

map = Array(n) { Array<String>(m) { "" } }

for (i in 0 until n) {
    val line = readLine()!!
    for (j in 0 until m) {
        map[i][j] = line[j].toString()
    }
}

저 같은 경우는 n과 m, cnt와 map은 전역변수로 두었고,

이에 대한 인풋값 할당은 main함수에서 진행하였습니다.

 

3. DFS

      

      

      

    
    

      <code />
    
fun dfs(x:Int, y:Int, team:String):Int {
    if(x >= n || x < 0 || y < 0 || y >= m)
        return 0

    if(map[x][y] == team) {
        cnt++

        map[x][y] = ""

        dfs(x - 1, y, team)
        dfs(x + 1, y, team)
        dfs(x , y - 1, team)
        dfs(x, y + 1, team)

        return cnt
    }

    return 0
}

첫 부분에서 x,y가 0과 n 범위 안에 있지 않다면 0을 리턴합니다.

 

그리고 해당 좌표의 값이 찾으려고 하는 팀의 값과 같을 때,

값을 ""로 만들어줍니다. 일종의 visited 역할을 한다 볼 수 있습니다.

 

이후 상하좌우에 대해 dfs를 호출하여 재귀적으로 함수를 수행하고,

 

cnt를 반환합니다.

 

 

      

      

      

    
    

      <code />
    
for(i in 0 until n) {
    for(j in 0 until m) {
        cnt = 0
        wPower += dfs(i, j, "W").toDouble().pow(2)
        cnt = 0
        bPower += dfs(i,j,"B").toDouble().pow(2)
    }
}

위에서 만든 함수를 사용하여 map의 모든 좌표에 대해 dfs를 수행합니다.

단, 저 같은 경우는 w팀과 b팀을 각각 수행하였습니다.

 

각 팀의 파워는 N명이 뭉쳐있을 때, N^2만큼의 파워를 낼 수 있다 하였으니, 제곱연산(pow(2))를 해주어 구할 수 있습니다.

 

      

      

      

    
    

      <code />
    
print("${wPower.toInt()} ${bPower.toInt()}")

 

최종적으로 도출한 값을 출력해주면 끝입니다.

 

 

 

4. 전체 소스코드

      

      

      

    
    

      <code />
    
import kotlin.math.pow

var n = 0
var m = 0
var cnt = 0
lateinit var map: Array<Array<String>>

fun main() {
    val nm = readLine()!!.split(" ")
    var wPower = 0.0
    var bPower = 0.0

    n = nm[1].toInt()
    m = nm[0].toInt()

    map = Array(n) { Array<String>(m) { "" } }

    for (i in 0 until n) {
        val line = readLine()!!
        for (j in 0 until m) {
            map[i][j] = line[j].toString()
        }
    }

    for(i in 0 until n) {
        for(j in 0 until m) {
            cnt = 0
            wPower += dfs(i, j, "W").toDouble().pow(2)
            cnt = 0
            bPower += dfs(i,j,"B").toDouble().pow(2)
        }
    }

    print("${wPower.toInt()} ${bPower.toInt()}")
}

fun dfs(x:Int, y:Int, team:String):Int {
    if(x >= n || x < 0 || y < 0 || y >= m)
        return 0

    if(map[x][y] == team) {
        cnt++

        map[x][y] = ""

        dfs(x - 1, y, team)
        dfs(x + 1, y, team)
        dfs(x , y - 1, team)
        dfs(x, y + 1, team)

        return cnt
    }

    return 0
}

 

 

---

5. 후기

 

DFS와 BFS 같은 그래프 탐색 문제에 좀 약했는데,

 

알고리즘 강의를 다시 듣고, 그래프 탐색 문제도 몇개 풀어보니 점점 익숙해져 가는군요.