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개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

출력

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

====

문제 분석

모든 칸을 탐색하면서 그래프 바깥으로 즉 x<0 || y<0 || x>=n  || y>=m  조건을 충족하는 좌표들의 수를 출력하면 되는 문제이다.

이때 모든 칸을 탐색할 때, 어떠한 칸에서 출발하여 이미 들렀던 곳이라면 방문 했던 흔적에 따라 이 지점을 따라가면 조건을 충족하는지, 못하는지 판단하여 중복 경로를 피할 수 있다. 따라서 visited 그래프에는 -1, 0 ,1 로 두어서 

-1 이라면 한 번도 방문한 적 없는 좌표,

 0 이라면 방문한 적 있는데 이 경로를 따라가면 실패할 좌표

 1 이라면 방문한 적이 있으며 이 경로를 따라가면 성공할 좌표라는 것을 뜻한다.

const visited = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => -1)
);

각 좌표에 써있는 방향에 따라 next X와 next Y를 설정하기 위한 상수를 선언해준다.

const dx = [0, 1, 0, -1]; // L , D , R , U
const dy = [-1, 0, 1, 0];
const dir = {
    L: 0,
    D: 1,
    R: 2,
    U: 3,
};

이 집합에는 성공적인 좌표들을 담아줄 집합이다. 추후에는 "x-y" 라는 문자열을 담아주어 중복을 처리할 것이다.

const succestSet = new Set();

모든 좌표를 탐색하면서 처음 방문한 곳이라면 탐색을 시작한다.

for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (visited[i][j] !== -1) {
                continue;
            }

아래는 현재 위치에서 다음으로 이동하면서 방문을 처리할 것이며, 성공적이라면 반복문 종료 후 visited에 그 좌표들을 1로 처리해준다.

const temp = [];
let [x, y] = [i, j];
let isSuccess = false;
while (true) {
    temp.push([x, y]);
    visited[x][y] = 0;
    const nextDir = dir[gr[x][y]];
    const nx = x + dx[nextDir];
    const ny = y + dy[nextDir];
    if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
        isSuccess = true;
        break;
    }
    if (visited[nx][ny] === 0) break;
    if (visited[nx][ny] === 1) {
        isSuccess = true;
        break;
    }
    visited[nx][ny] = 0;
    x = nx;
    y = ny;
}
if (isSuccess) {
    for (const [x, y] of temp) {
        succestSet.add(`${x}-${y}`);
        visited[x][y] = 1;
    }
}

정답 코드

const dx = [0, 1, 0, -1]; // L , D , R , U
const dy = [-1, 0, 1, 0];
const dir = {
    L: 0,
    D: 1,
    R: 2,
    U: 3,
};

const main = (n, m, gr) => {
    const visited = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => -1)
    );
    const succestSet = new Set();
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (visited[i][j] === 1) {
                continue;
            }
            if (visited[i][j] === 0) continue;
            const temp = [];
            let [x, y] = [i, j];
            let isSuccess = false;
            while (true) {
                temp.push([x, y]);
                visited[x][y] = 0;
                const nextDir = dir[gr[x][y]];
                const nx = x + dx[nextDir];
                const ny = y + dy[nextDir];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                    isSuccess = true;
                    break;
                }
                if (visited[nx][ny] === 0) break;
                if (visited[nx][ny] === 1) {
                    isSuccess = true;
                    break;
                }
                visited[nx][ny] = 0;
                x = nx;
                y = ny;
            }
            if (isSuccess) {
                for (const [x, y] of temp) {
                    succestSet.add(`${x}-${y}`);
                    visited[x][y] = 1;
                }
            }
        }
    }
    console.log(succestSet.size);
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map((v) => +v);
const gr = input.slice(1).map((v) => v.split(''));
main(n, m, gr);