백준 2115 갤러리 Kotlin (구현)

문제 출처 : https://www.acmicpc.net/problem/2115

2115번: 갤러리

문제

갤러리의 지도는 M*N의 정사각형 격자로 표현될 수 있다. 어떤 정사각형들은 벽으로 구성되어 있고, 다른 정사각형들은 빈 공간으로 구성되어 있다. 벽을 회색, 빈 공간을 흰색으로 표현하면 다음 그림과 같다.

갤러리에 그림을 걸려고 한다. 그림의 길이는 정사각형의 변의 길이의 두 배이다. 반드시 빈 공간과 인접해 있는 벽에만 그림을 걸 수 있으며, 그림들은 서로 겹칠 수 없다. 갤러리의 맵이 주어졌을 때, 최대로 걸 수 있는 그림의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 갤러리의 세로 길이 M과 가로 길이 N이 주어진다. (1 ≤ M, N ≤ 1,000) 다음 M개의 줄에는 각각 N개의 문자가 주어진다. 문자는 'X' 또는 '.'이며 'X'는 벽을, '.'는 빈 공간을 나타낸다.

입력되는 모든 데이터에서 적어도 첫 줄과 마지막 줄, 첫 열과 마지막 열은 모두 벽이다.

출력

최대 그림 개수를 출력한다.

알고리즘 분류

• 구현

풀이

그래프 탐색에 근거한 구현 문제이다.

우선 몇 가지 케이스를 살펴보자.

 

..  처럼 .이 좌우로 있다고 하자.

 

왼쪽 .에서 오른쪽 .으로 갈 땐,

xx

..  

xx

이처럼 현재 점, 다음 점의 상, 하 벽을 확인하면 된다.

위와 같은 경우 위, 아래 두 개의 그림을 걸 수 있는 것이다.

 

마찬가지로 위의 .에서 아래 .으로 갈 땐,

x.x

x.x

이처럼 현재 점, 다음 점의 좌, 우 벽을 확인하면 된다.

위와 같은 경우 좌,우로 두 개의 그림을 걸 수 있다.

 

처음 생각한 풀이는 bfs에서 큐에 현재 노드의 좌표와, 이전 노드의 상,하,좌,우 벽 상태를 저장했다.

이 풀이의 문제는 같은 노드를 어느 방향에서 들어오느냐에 따라 답이 달라질 수 있다는 점이다.

 

이를 해결하기 위해, visited[n][m][4]를 만들어, 방문 체크를 4방향으로 해주었다.

이 경우, 여러 방향에서 해당 노드를 들어오는 경우를 탐색할 수 있지만, 노드들의 벽 상태를 제대로 저장하기 힘들었다.

 

이후, .인 노드들의 상하좌우를 검사하여 벽인 곳을 저장해놓고, 이후에 따로 .에 대해 bfs로 그림 검사(메모리 초과),

그림 따로 저장하지 않고, 현재 노드에서 다음 노드로 이동할 수 있을 때(현재가 .이고 다음 노드도 .일 때), 주어진 입력 graph의 X를 비교하는 방식(틀림)

등의 시도를 해보며 대부분의 시간을 잘못된 케이스를 찾으며 bfs 방식을 고치는 데에 사용했지만, 반례를 찾지 못했다.

 

결국 킹갓 MMM님의 도움을 받아 해결했는데,

우선 bfs로 할 필요가 없었다.

정확히 말하자면 굳이 bfs로 해서 해당 노드를 여러 방향으로 들어가는 경우를 고려할 필요가 없었다.

내 기존 풀이에 대한 반례도 찾아주셨는데, 여기서 어디 부분의 그림이 잘못된 건지 찾기는 무리였다.

아무튼, bfs 대신, 그래프를 왼쪽위부터 순서대로 .인 부분을 탐색하며, .이라면 findWall 함수를 실행해서,

현재 노드(.)와 인접한 노드(.)과의 벽만 비교해주면 됐다.

 

그림을 찾고, 그림을 벽에 거는 것에 대한 구현은

위에 설명처럼, 상,하 이동시 좌,우 벽 확인, 좌,우 이동시 상,하 벽 확인 해주었고,

벽에 그림을 걸 수 있다면, visited[r][c][i] (현재노드 i방향 벽), visited[nr][nc][i] (다음 노드 i방향 벽)을 true 처리해 주었다.

코드(통과)

import java.util.*

//상, 하 방향으로 이동시 전 칸의 좌 우 벽 값이 필요
//좌, 우 방향으로 이동시 전 칸의 상 하 벽 값잋 필요
var answer = 0
val dir = arrayOf(
    arrayOf(1,0),
    arrayOf(-1,0),
    arrayOf(0,1),
    arrayOf(0,-1)
)

data class Node(var r : Int, var c: Int)

fun findWall(i : Int, j : Int, graph : Array<CharArray>, visited : Array<Array<BooleanArray>>){

        val r=i
        val c=j
        //다음 . 과 현재 . 사이 그림 가능한지 확인
        for(i in 0 until 4){
            val nr = r+dir[i][0]
            val nc = c+dir[i][1]
            if(visited[nr][nc][i]) continue
            if(graph[nr][nc]=='.'){
                //그림 걸 수 있는지 검사
                //상하 이동 -> 좌우벽만 필요
                if(i<2){
                    //j :우좌
                    for(j in 2 until 4){
                        if(graph[r+dir[j][0]][c+dir[j][1]]=='X' && graph[nr+dir[j][0]][nc+dir[j][1]]=='X'){
                            if(visited[r+dir[j][0]][c+dir[j][1]][j] || visited[nr+dir[j][0]][nc+dir[j][1]][j]) continue
                            answer++
                            visited[r+dir[j][0]][c+dir[j][1]][j] =true
                            visited[nr+dir[j][0]][nc+dir[j][1]][j] =true
                        }
                    }
                }
                //좌우 이동 -> 상하벽만 필요
                else{
                    //j : 하상
                    for(j in 0 until 2){
                        if(graph[r+dir[j][0]][c+dir[j][1]]=='X' && graph[nr+dir[j][0]][nc+dir[j][1]]=='X'){
                            if(visited[r+dir[j][0]][c+dir[j][1]][j] || visited[nr+dir[j][0]][nc+dir[j][1]][j]) continue
                            answer++
                            visited[r+dir[j][0]][c+dir[j][1]][j] =true
                            visited[nr+dir[j][0]][nc+dir[j][1]][j] =true
                        }
                    }
                }
            }
        }

}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val graph = Array(n){
        val sen = br.readLine()
        CharArray(m){
            sen[it]
        }
    }

    val visited = Array(n){Array(m){BooleanArray(4)} }
    for(i in 1 until graph.size){
        for(j in 1 until graph[i].size){
            if(graph[i][j]=='.'){
                findWall(i,j,graph,visited)
            }
        }
    }

    write("$answer")
    close()
}

코드(틀림)

import java.util.*

//상, 하 방향으로 이동시 전 칸의 좌 우 벽 값이 필요
//좌, 우 방향으로 이동시 전 칸의 상 하 벽 값잋 필요
var answer = 0
val dir = arrayOf(
    arrayOf(1,0),
    arrayOf(-1,0),
    arrayOf(0,1),
    arrayOf(0,-1)
)

data class Node(var r : Int, var c: Int)

fun bfs(i : Int, j : Int, n : Int, m : Int, graph : Array<CharArray>, visited : Array<BooleanArray>, visited1 : Array<Array<BooleanArray>>){
    visited[i][j]=true

    val q : Queue<Node> = LinkedList<Node>()
    q.add(Node(i,j))
    while(q.isNotEmpty()){
        val cur = q.poll()
        //다음 . 이동
        for(i in 0 until 4){
            val nr = cur.r+dir[i][0]
            val nc = cur.c+dir[i][1]
            if(visited1[nr][nc][i]) continue
            if(graph[nr][nc]=='.'){
                //그림 걸 수 있는지 검사
                //상하 이동 -> 좌우벽만 필요
                if(i<2){
                    //j :우좌
                    for(j in 2 until 4){
                        if(graph[cur.r+dir[j][0]][cur.c+dir[j][1]]=='X' && graph[nr+dir[j][0]][nc+dir[j][1]]=='X'){
                            if(visited1[cur.r+dir[j][0]][cur.c+dir[j][1]][j] || visited1[nr+dir[j][0]][nc+dir[j][1]][j]) continue
                            answer++
                            visited1[cur.r+dir[j][0]][cur.c+dir[j][1]][j] =true
                            visited1[nr+dir[j][0]][nc+dir[j][1]][j] =true
                        }
                    }
                }
                //좌우 이동 -> 상하벽만 필요
                else{
                    //j : 하상
                    for(j in 0 until 2){
                        if(graph[cur.r+dir[j][0]][cur.c+dir[j][1]]=='X' && graph[nr+dir[j][0]][nc+dir[j][1]]=='X'){
                            if(visited1[cur.r+dir[j][0]][cur.c+dir[j][1]][j] || visited1[nr+dir[j][0]][nc+dir[j][1]][j]) continue
                            answer++
                            visited1[cur.r+dir[j][0]][cur.c+dir[j][1]][j] =true
                            visited1[nr+dir[j][0]][nc+dir[j][1]][j] =true
                        }
                    }
                }
                q.add(Node(nr,nc))
                visited1[nr][nc][i]=true
                visited[nr][nc]=true
            }
        }
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val graph = Array(n){
        val sen = br.readLine()
        CharArray(m){
            sen[it]
        }
    }
    //visited1는 bfs 탐색중 같은 방향으로 진입하는 노드 스킵
    val visited1 = Array(n){Array(m){BooleanArray(4)} }
    //visited는 bfs 시작 중복 제거
    val visited = Array(n){BooleanArray(m)}
    for(i in 1 until graph.size){
        for(j in 1 until graph[i].size){
            if(graph[i][j]=='.'){
                if(visited[i][j]) continue
                bfs(i,j,n,m,graph,visited,visited1)
            }
        }
    }

    write("$answer")
    close()
}