백준 2178번 미로 탐색 코틀린 BFS

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

2178번: 미로 탐색

 

안녕하세요! 오늘은 미로 탐색 문제를 풀어봤습니다!

 

제목을 보면 대충 유추할 수 있듯이 

 

이 문제는 BFS 를 이용해서 풀어야하는 문제입니다!

 

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1 

4 6

101111

101010

101011

111011

예제 출력 1 

15

예제 입력 2 

4 6

110110

110110

111111

111101

예제 출력 2 

9

예제 입력 3 

2 25

1011101110111011101110111

1110111011101110111011101

예제 출력 3 

38

예제 입력 4 

7 7

1011111

1110001

1000001

1000001

1000001

1000001

1111111

 

---

이 문제는 (N,M) 까지 가는 최단 거리를 구하는 문제입니다 즉 BFS를 이용해야하는 문제라는 의미입니다!

 

import java.util.*

var visited : Array<BooleanArray> = arrayOf()

var graphs : Array<IntArray> = arrayOf()
var dx = intArrayOf(-1,0,1,0)
var dy = intArrayOf(0,-1,0,1)

class Pointer( var x : Int = 0,
               var y : Int = 0)

fun main() {

    var temp = readLine()

    var array = temp!!.split(" ").map { it.toInt() }

    visited = Array(array[0]+2){ BooleanArray(array[1]+2) }
    graphs = Array(array[0]+2){ IntArray(array[1]+2) }

    for(i in 1 .. array[0]){
        var temp  = readLine()!!.toCharArray()

        for(j in 1 .. array[1]){
            graphs[i][j] = Integer.parseInt(temp.get(j-1).toString())
        }
    }

    bfs(1,1)

    println(graphs[array[0]][array[1]])
}

fun bfs(x : Int, y : Int){
    var queue = LinkedList<Pointer>()
    queue.add(Pointer(x,y))
    visited[x][y]=true
    while (queue.isNotEmpty()){
        var pointer = queue.poll()
        for(i in 0 until 4){

            var tempX = pointer.x+dx[i]
            var tempY = pointer.y+dy[i]

            if(graphs[tempX][tempY]!=0 && !visited[tempX][tempY]){
                visited[tempX][tempY] =true
                graphs[tempX][tempY] = graphs[pointer.x][pointer.y]+1
                queue.add(Pointer(tempX,tempY))
            }
        }
    }
}

 

코드를 보면 

행과 열에 크기를 입력값에 비해서 +2 만큼 더해서 그래프의 크기를 할당했는대 

그 이유는 미로 외곽을 벽으로 나타내기 위해서입니다!

즉

 

예제 1번 을 기준으로 한다면 

00000000
01011110
01010100
01010110
01110110
00000000

이런 형태가 됩니다 

 

물론 외곽을 0으로 표시 안해도 상관없지만

그렇게 되면 각 방향 별 이동 시 미로외곽을 넘어가는지 안넘어가는지 별도의 if문이 필요합니다! 

좀 더 간단하게 if문을 줄이고 싶어서 저는 외곽을 0으로 표시하고 문제를 풀었습니다!