[백준 2206] - 벽 부수고 이동하기(Kotlin)[골드3]

문제

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

2206번: 벽 부수고 이동하기

 

문제 풀이

난이도 있는 DFS, BFS 문제의 특징이라고 할 수 있다.

DP와 같이 사용하거나, 삼차원 배열을 통한 방문 체크, 우선순위 큐 같은 경우가 있다.

해당 문제는 삼차원 배열을 통해서 벽을 부순 여부를 가지고 방문을 체크하는 것이 중요하다.

일반적인 이차원 배열로 방문처리를 할 경우 똑같은 좌표를 방문했지만,

해당 좌표를 이동하기 위해서 벽을 부순건지, 부수지 않았는지가 중요하기 때문이다.

 

방문처리는 삼차원 배열로 선언했다.

visit[N][M][2] --> N은 열의 크기, M은 행의 크기, 2는 벽을 부쉈는지, 안 부쉈는지를 뜻한다.
즉 z가 0이라면 벽을 부수지 않은 것이고, 1이라면 벽을 부순것이다.

삼차원 배열로 방문처리를 할 생각까지 도달했다면 해당 문제는 정말 쉬운 문제이다.

그렇다면 큐에는 어떤 것이 들어가야 할까?

Queue <X, Y, Wall, room> -> X는 x좌표, Y는 y좌표, Wall은 벽을 부쉈는지 안 부쉈는지를 의미, room은 지나간 칸의 개수이다.

방문처리를 할 경우 해당 큐에서 원소를 뽑고 visit [x][y][wall]을 하면 될 것이다.

 

나는 큐에 넣을 data class를 하나 생성해서 선언해 줬다.

    data class Move(val x: Int, val y : Int, val wall : Int, val room : Int){
        override fun toString(): String {
            return "x : $x y: $y wall : $wall room: $room"
        }
    }

 

1. 이동하려는 좌표가 벽인데, 벽을 부수지 않았다면 큐에 넣는다.
2. 이동하려는 좌표가 빈 공간이라면 그대로 큐에 넣는다.

나머지의 경우 모두 무시하면 된다.

전체 코드

package Graph.`2206_벽_부수고_이동하기`.LJH

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

class `2206` {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private var n=0
    private var m=0
    private var answer=-1
    private lateinit var visit : Array<Array<IntArray>>
    private lateinit var graph : Array<Array<Int>>
    var q : Queue<Move> = LinkedList()
    val x = arrayOf(1,-1,0,0)
    val y = arrayOf(0,0,1,-1)
    init{
        input()
        bfs()
        print(answer)
    }
    private fun input()
    {
        br.readLine().split(" ").forEachIndexed { index, s ->
            when(index){
                0 -> n=s.toInt()
                1->m=s.toInt()
            }
        }
        if(n==1 && m==1)
            answer=1
        graph = Array(n){ Array(m,{0})}
        visit = Array(n){ Array(m) {IntArray(2,{-1}) }}
        for(i in 0 until n){
            val line = br.readLine().toString()
            for(j in 0 until m){
                graph[i][j] = line[j].digitToInt()
            }
        }
    }

    private fun bfs(){
        q.add(Move(0,0,0,1))
        while(!q.isEmpty()){
            val now = q. poll()
            //println("now : $now")
            if(visit[now.x][now.y][now.wall]!=-1)
                continue
            visit[now.x][now.y][now.wall]=now.room
            for(dir in 0 until 4){
                val moveX = now.x+x[dir]
                val moveY = now.y+y[dir]
                if(moveX !in graph.indices || moveY !in graph[0].indices) //범위가 아닐 때
                    continue
                if(moveX==n-1 && moveY == m-1){
                    answer=now.room+1
                    return
                }
                if(now.wall==1 && graph[moveX][moveY]==1) //벽을 이미 깨부수고, 가는 곳이 벽일 경우 못감
                    continue
                if(visit[moveX][moveY][now.wall]!=-1) //이미 방문했다면
                    continue
                if(now.wall==0 && graph[moveX][moveY]==1){
                    q.add(Move(moveX,moveY,1,now.room+1))
                }
                else if(now.wall==0 && graph[moveX][moveY]==0)
                    q.add(Move(moveX,moveY,0,now.room+1))
                else
                    q.add(Move(moveX,moveY,now.wall,now.room+1))
            }
        }
    }
    data class Move(val x: Int, val y : Int, val wall : Int, val room : Int){
        override fun toString(): String {
            return "x : $x y: $y wall : $wall room: $room"
        }
    }
}

fun main(){
    val solution = `2206`()
}