코딩테스트 / 미로 탈출

 

https://school.programmers.co.kr/learn/courses/30/lessons/159993

너비우선탐색(BFS) 문제입니다. 
너비우선탐색은 큐(선입 선출)로 풀 수 있습니다. 

 

파이썬

def find_s_l_e(maps):
    point_s, point_l, point_e = (0, 0), (0, 0), (0, 0)
    for r, row in enumerate(maps):
        for c, col in enumerate(row):
            if col == 'S':
                point_s = (r, c)
            elif col == 'L':
                point_l = (r, c)
            elif col == 'E':
                point_e = (r, c)
    return point_s, point_l, point_e


def bfs(maps, start, end):
    queue = [(*start, 0)]
    visited = set()
    while queue:
        r, c, length = queue.pop(0)
        if (r, c) in visited:
            continue
        visited.add((r, c))
        if (r, c) == end:
            return length
        length += 1
        for diff_r, diff_c in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_r = r + diff_r
            new_c = c + diff_c
            if 0 <= new_r < len(maps) and 0 <= new_c < len(maps[0]) and maps[r][c] != 'X':
                queue.append((new_r, new_c, length))
    return -1


def solution(maps):
    point_s, point_l, point_e = find_s_l_e(maps)
    length1 = bfs(maps, point_s, point_l)
    length2 = bfs(maps, point_l, point_e)
    return -1 if length1 == -1 or length2 == -1 else length1 + length2

 

코틀린

import java.util.*
import kotlin.collections.HashSet

class Solution {
    private fun findSLE(maps: Array<String>): Triple<Pair<Int, Int>, Pair<Int, Int>, Pair<Int, Int>> {
        var pointS = Pair(0, 0)
        var pointL = Pair(0, 0)
        var pointE = Pair(0, 0)
        for (i in maps.indices)
            for (j in maps[i].indices)
                when (maps[i][j]) {
                    'S' -> pointS = Pair(i, j)
                    'L' -> pointL = Pair(i, j)
                    'E' -> pointE = Pair(i, j)
                }
        return Triple(pointS, pointL, pointE)
    }

    private fun bfs(maps: Array<String>, start: Pair<Int, Int>, end: Pair<Int, Int>): Int {
        val diff = arrayOf(Pair(1, 0), Pair(-1, 0), Pair(0, 1), Pair(0, -1))
        val queue: Queue<Triple<Int, Int, Int>> = LinkedList()
        queue.add(Triple(start.first, start.second, 0))
        val visited = HashSet<Pair<Int, Int>>()
        while (queue.isNotEmpty()) {
            var (r, c, length) = queue.poll()
            val rc = Pair(r, c)
            if (rc in visited)
                continue
            visited.add(rc)
            if (rc == end)
                return length
            length++
            for ((diffR, diffC) in diff) {
                val newR = r + diffR
                val newC = c + diffC
                if ((0 <= newR && newR < maps.size) && (0 <= newC && newC < maps[0].length) && (maps[r][c] != 'X'))
                //if ((newR in maps.indices) && (newC in maps[0].indices) && (maps[r][c] != 'X'))
                    queue.add(Triple(newR, newC, length))
            }
        }
        return -1
    }

    fun solution(maps: Array<String>): Int {
        val (pointS, pointL, pointE) = findSLE(maps)
        val length1 = bfs(maps, pointS, pointL)
        val length2 = bfs(maps, pointL, pointE)
        return if (length1 == -1 || length2 == -1) -1 else length1 + length2
    }
}