[Kotlin] BOJ2234 성곽

DFS, BFS 둘 다 풀 수 있는 문제

(링크 : https://www.acmicpc.net/problem/2234)

2234번: 성곽

비트마스킹으로 BFS의 방향을 나타내는 방법이 힌트에 나와있었지만
비트마스킹이 뭔지 몰랐기에 그냥 하던대로 구현을 하려고 했지만,, 메모리 초과의 벽을 넘지 못했다..

◆ 기존 구현 방법
각 좌표에 있는 번호를 when으로 분기문으로 8,4,2,1 숫자를 순서대로 0이 될때 까지
빼줌으로써 방향을 구하는 방식을 사용함 근데 이 과정에서 변수 할당과 리스트 생성이
비스마스킹 알고리즘을 사용하는 경우보다 잦아서, 메모리 초과가 나왔다. (답은 나옴)

◆ 해결 방법
비트마스킹을 사용하여
각 비트에 해당 숫자가 포함되어있는지 확인하는 방법으로 벽이 있는지 검사
for (z in 0 until 4){
    k = (1 shl z) // 1,2,4,8 //shl = 시프트 연산자
    if ((map[point.y][point.x] and k) != 0) continue // 벽 체크 (벽이 있으면 무시)
}

◆ 벽을 허무는 방법
map[i][j] = map[i][j] - k
해당 좌표값에 벽의 위치에 해당하는 수를 제거

◆ 추가로 느낀점
 MY, MX 배열 방향을 정할때 그냥 기존에 짜두었던 코드를 복붙하는 방식으로 썼는데
 이런 문제처럼 검사하는 방향을 명시해주었다면 그 방향 순서로 정의해두는게 코드짜기 편하다.

소스코드(BFS)

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader
import java.lang.Math.max
import java.util.*

private val MY = arrayOf(0,-1,0,1) //서(좌) 북(아래) 동(우) 남(위)
private val MX = arrayOf(-1,0,1,0) //서(좌) 북(아래) 동(우) 남(위)

private var N = 0 //가로 //(1 ≤ M, N ≤ 50)
private var M = 0 //세로
private lateinit var map : List<IntArray>
private lateinit var isVisited : List<BooleanArray>
private val Q :Queue<Point> = LinkedList()
private var roomAreaWidth = 1
private val roomAreaWidthList = mutableListOf<Int>()
private var biggestAreaWidth = 1

private fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    map = List(M){br.readLine().split(" ").map { it.toInt() }.toIntArray()}
    isVisited = List(M) { BooleanArray(N){false} }

    for (i in 0 until M){
        for (j in 0 until N){
            if (isVisited[i][j] == false){
                Q.add(Point(i, j))
                isVisited[i][j] = true
                bfs()
                roomAreaWidthList.add(roomAreaWidth)
                roomAreaWidth = 1
            }
        }
    }

    for (i in 0 until M){
        for (j in 0 until N){
            clearVisited()
            //벽이 있는 경우만 (비트 연산)
            var k = 1
            for (z in 0 until 4){
                k = (1 shl z) // 1,2,4,8

                if((map[i][j] and k) == k) { //해당 벽을 가지고 있다면
                    isVisited[i][j] = true

                    //벽 없애기
                    map[i][j] = map[i][j] - k

                    Q.add(Point(i, j))
                    bfs()
                    biggestAreaWidth = max(roomAreaWidth, biggestAreaWidth)
                    roomAreaWidth = 1

                    //벽 다시 만들기
                    map[i][j] = map[i][j] + k
                }

            }
        }
    }

    println(roomAreaWidthList.size)
    println(roomAreaWidthList.maxOf { it })
    println(biggestAreaWidth)

    /*
    출력물 :
    이 성에 있는 방의 개수 ==> 기존 DFS, BFS로 구하기 가능
    가장 넓은 방의 넓이 ==> 기존 DFS, BFS로 구하기 가능
    하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
    ==> 벽을 하나씩 제거한 상태로 DFS 혹은 DFS
    */
}
private fun bfs(){
    while (Q.isNotEmpty()){
        val point = Q.poll()
        var k = 1
        for (i in 0 until 4) {
            k = (1 shl i) // 1,2,4,8 //서,북,동,남
            if ((map[point.y][point.x] and k) != 0) continue // 벽 체크 (벽이 있으면 무시)
            val nextY = point.y + MY[i]
            val nextX = point.x + MX[i]
            //맵 안인가? , 둘 사이에 벽은 없는가? , 가보지 않은 곳인가?
            if (isInMap(nextY,nextX) && (isVisited[nextY][nextX] == false)){
                Q.add(Point(nextY, nextX))
                roomAreaWidth++
                isVisited[nextY][nextX] = true
            }
        }
    }
}

private fun isInMap(y :Int, x :Int) = (y in 0 until M) && (x in 0 until N)

private fun clearVisited(){
    for (i in isVisited.indices){
        for (j in isVisited[i].indices){
            isVisited[i][j] = false
        }
    }
}

data class Point(
    val y :Int,
    val x :Int
)