[알고리즘] 알고스팟 (백준 1261번)

1261번: 알고스팟

 처음엔 이분탐색을 이용해야하는 줄 알았는데 시간 초과, 메모리 초과가 났다. 이후에 BFS로 풀었는데 원래는 다익스트라 문제다. 결론적으로 다익스트라가 시간, 메모리가 더 적게 걸린다.

 

Solution

1. BFS 버전

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

import java.util.*

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var x = arrayOf(-1, 1, 0, 0)
var y = arrayOf(0, 0, -1, 1)

var N = 0
var M = 0
lateinit var map : Array<Array<Int>>

fun solution() {

    var strtok = StringTokenizer(br.readLine())
    M = strtok.nextToken().toInt()
    N = strtok.nextToken().toInt()

    map = Array(N+1, {Array(M+1, {0})})

    for(i in 1..N)
    {
        var str = br.readLine()

        for(j in 1..M)
            map[i][j] = (str[j - 1] - '0')
    }

    bw.write(bfs().toString())
}

fun bfs() : Int
{
    var visited_min = Array(N + 1, {Array(M + 1, {N * M + 1})})
    visited_min[1][1] = 0

    var queue : Queue<Position> = LinkedList()
    queue.offer(Position(1, 1, 0))

    while(!queue.isEmpty())
    {
        var now = queue.poll()
        //println(now.toString())

        for(i in 0..3)
        {
            var next_x = now.x + x[i]
            var next_y = now.y + y[i]

            if(next_x in 1..N && next_y in 1..M)
            {
                //println("$next_x $next_y ${now.destory}")
                if(visited_min[next_x][next_y] > now.destory)
                {
                    visited_min[next_x][next_y] = now.destory

                    if(next_x == N && next_y == M)
                        continue

                    if(map[next_x][next_y] == 1)
                        queue.offer(Position(next_x, next_y, now.destory + 1))
                    else
                        queue.offer(Position(next_x, next_y, now.destory))
                }

            }
        }
    }

    return visited_min[N][M]
}


data class Position(var x : Int, var y : Int, var destory : Int)


fun main() {
    solution()
    br.close()
    bw.close()
}

 BFS로 푼 버전은 그 다음 이동할 노드에 최소로 벽을 부수고 온 Position만 방문을 할 수 있게 해주는 것이다. 즉, 누군가 방문했는지 여부와는 관계없이 더 적게 벽을 부수고 온 애들은 얼마든지 재방문이 가능하다.

 

2. 다익스트라 버전

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

import java.util.*

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var x = arrayOf(-1, 1, 0, 0)
var y = arrayOf(0, 0, -1, 1)

var N = 0
var M = 0
lateinit var map : Array<Array<Int>>
lateinit var dist : Array<Array<Int>>

var wall_max = 0

fun solution() {

    var strtok = StringTokenizer(br.readLine())
    M = strtok.nextToken().toInt()
    N = strtok.nextToken().toInt()

    map = Array(N+1, {Array(M+1, {0})})

    for(i in 1..N)
    {
        var str = br.readLine()

        for(j in 1..M)
        {
            map[i][j] = (str[j - 1] - '0')
            wall_max++
        }
    }


    dist = Array(N+1, {Array(M+1, {wall_max})})
    dist[1][1] = 0
    dijkstra()

    bw.write(dist[N][M].toString())
}

fun dijkstra()
{
    var queue = PriorityQueue<Position>(kotlin.Comparator { o1, o2 -> o1.destory - o2.destory })
    queue.offer(Position(1, 1, 0))
    var visited = Array(N + 1, {Array(M + 1, {false})})

    while (!queue.isEmpty())
    {
        var now = queue.poll()

        if(visited[now.x][now.y])
            continue
        visited[now.x][now.y] = true

        for(i in 0..3)
        {
            var next_x = now.x + x[i]
            var next_y = now.y + y[i]

            if(next_x in 1..N && next_y in 1..M)
            {
                if(dist[next_x][next_y] > dist[now.x][now.y] + map[now.x][now.y])
                {
                    dist[next_x][next_y] = dist[now.x][now.y] + map[now.x][now.y]

                    if(!visited[next_x][next_y])
                        queue.offer(Position(next_x, next_y, dist[next_x][next_y]))
                }
            }
        }
    }
}


data class Position(var x : Int, var y : Int, var destory : Int)


fun main() {
    solution()
    br.close()
    bw.close()
}

 다익스트라는 간선의 가중치를 벽이 있으면 1, 없으면 0으로 여겨서 최소로 벽을 부수고 목표지점에 도착하는 원리이다. weight 대신 map의 입력값을 가중치로 두고 비교를 하면 된다.