백준 17090 미로 탈출하기 Kotlin (dfs,bfs)

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

17090번: 미로 탈출하기

문제

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.

어떤 칸(r, c)에 적힌 문자가

• U인 경우에는 (r-1, c)로 이동해야 한다.
• R인 경우에는 (r, c+1)로 이동해야 한다.
• D인 경우에는 (r+1, c)로 이동해야 한다.
• L인 경우에는 (r, c-1)로 이동해야 한다.

미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

입력

첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

출력

첫째 줄에 탈출 가능한 칸의 수를 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

풀이

dfs, bfs 등의 그래프 탐색으로 풀 수 있는 문제이다.

다만, 문제에선 모든 점을 시작점으로 검사해야 하니, 일반적인 방법으로는 시간 초과가 뜰 것이고,

어떠한 좌표를 방문했을 때, 이전 과정이 어쨌든 해당 좌표에서 나아갈 길은 정해져있으니,

방문한 좌표에 방문했는지, 해당 좌표를 방문하면 탈출 가능한지 등의 정보를 저장하는 메모이제이션 기법을 사용하면,

탐색 횟수가 훨씬 줄어든다.

 

dfs 풀이는 다음과 같다.

visited[r][c] = 2  // graph[r][c]는 탈출 가능(방문 함)

visited[r][c] = 1 // graph[r][c]는 탈출 불가(방문 함)

visited[r][c] = 0 // 아직 graph[r][c]를 방문 안 함

 

모든 좌표에 대해 dfs를 돌린다.

만약 해당 좌표가 이미 방문했다면, 스킵한다.

dfs로 들어가서, 다음 좌표가 그래프를 벗어난다면, isEscaped =true 로 탈출 가능하단 표시를 해주고,

재귀로 들어온 depth를 다시 올라가며, 해당 좌표까지 오는 길을 모두 visited[r][c] =2 처리해 주고, answer를 증가시킨다.

만약 다음 좌표가 방문한 좌표이고, visited[nr][nc] = 2 라면 isEscaped =true, 이전 길 visited[r][c]= true 처리하고,

visited[nr][nc] =1 이라면 그냥 돌아간다.

 

만약 다음 좌표가 방문하지 않은 좌표고 그래프 내에 있는 좌표라면 그냥 visite[nr][nc] =1로 방문 처리해 주고, 다음 좌표를 이어 탐색한다.

 

bfs 풀이는 다음과 같다.

dfs 풀이와 비슷하다.

하지만 bfs에서는 지나온 길을 알 방법이 없으므로, q에서 다음 좌표로 넘어가기 전에, 다른 큐에 이전 좌표들을 넣어준다. 해당 좌표에서 시작된 길이 탈출로 이어진다면, 이전 좌표들을 모두 탈출 가능 처리한다.

여기선 visited 배열과 escape 배열을 따로 뒀지만, dfs 풀이처럼 visited 배열에 0,1,2 값을 저장하여 풀어도 된다.

 

유니온 파인드를 이용해 풀 수도 있으나, 굳이? 란 생각이 든다.

 

코드(dfs)

//3<=n,m<=500
//visited 2 : 탈출 가능 1 : 탈출 불가 0 : 미방문
val visited = Array<IntArray>(500){ IntArray(500) }//방문 체크
val moving = mapOf(
    'U' to Pair(-1,0),
    'R' to Pair(0,1),
    'D' to Pair(1,0),
    'L' to Pair(0,-1))
var answer=0
var isEscaped=false

fun dfs(r : Int, c : Int, n : Int, m : Int, graph : Array<String>){
    var nr = r + moving[graph[r][c]]!!.first
    var nc = c + moving[graph[r][c]]!!.second
    if(nr !in 0 until n || nc !in 0 until m){
        isEscaped = true
        visited[r][c]=2
        answer++
        return
    }
    if(visited[nr][nc]!=0){
        if(visited[nr][nc]==2) {
            isEscaped = true
            visited[r][c]=2
            answer++
        }
        return
    }
    visited[nr][nc]=1
    dfs(nr,nc,n,m,graph)
    if(isEscaped){
        visited[r][c]=2
        answer++
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map { it.toInt() }
    val graph = Array<String>(n){""}
    //input
    for(i in 0 until n){
        graph[i] = br.readLine()
    }
    //solve
    for(i in 0 until n){
        for(j in 0 until m){
            if(visited[i][j]!=0){
                continue
            }
            dfs(i,j,n,m,graph)
            isEscaped=false
        }
    }

    write("$answer")

    close()
}

코드(bfs)

import java.util.*

//3<=n,m<=500
val visited = Array<BooleanArray>(500){BooleanArray(500)}//방문 체크
val escape = Array<BooleanArray>(500){BooleanArray(500)}//해당 노드 탈출 가능 여부
val moving = mapOf<Char,Pair<Int,Int>>('U' to Pair(-1,0), 'R' to Pair(0,1), 'D' to Pair(1,0), 'L' to Pair(0,-1))
var answer=0
fun bfs(i : Int, j : Int,n :Int, m : Int, graph : Array<String>){
    val q : Queue<Pair<Int,Int>> = LinkedList<Pair<Int,Int>>()//나아갈 길들
    val way : Queue<Pair<Int,Int>> = LinkedList<Pair<Int,Int>>()//지나온 길들
    q.add(Pair(i,j))
    way.add(Pair(i,j))
    visited[i][j] =true

    while(q.isNotEmpty()){

        var (r,c) = q.poll()
        val nr = r+ moving[graph[r][c]]!!.first
        val nc = c+ moving[graph[r][c]]!!.second

        if(nr !in 0 until n || nc !in 0 until m){ //nr,nc가 탈출한 경우
            while(way.isNotEmpty()){//지나온 길들은 모두 탈출 가능
                val (rr,cc) = way.poll()
                escape[rr][cc]=true
                answer++
            }
            return
        }
        if(visited[nr][nc]){ //이미 방문한 경우
            if(escape[nr][nc]){//방문한 칸이 탈출 가능한 경우
                while(way.isNotEmpty()){
                    val (rr,cc) = way.poll()
                    escape[rr][cc]=true
                    answer++
                }
            }
            return
        }
        //다음 탐색
        visited[nr][nc]=true
        q.add(Pair(nr,nc))
        way.add(Pair(nr,nc))
    }

}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map { it.toInt() }
    val graph = Array<String>(n){""}
    //input
    for(i in 0 until n){
        graph[i] = br.readLine()
    }
    //solve
    for(i in 0 until n){
        for(j in 0 until m){
            if(visited[i][j]){
                continue
            }
            bfs(i,j,n,m,graph)
        }
    }
    write("$answer")

    close()
}