https://softeer.ai/practice/6275
현대자동차그룹에 입사하여 로봇 연구 개발 부서에 막 입사한 당신은 아래와 같은 기능을 하는 간단한 로봇의 사용법을 전달받았다. 로봇은 H행 W열의 2차원 격자판 위를 돌아다닌다. 격자판의 각 칸은 정사각형 모양이며, 로봇은 격자판의 칸 하나를 차지한다. 로봇은 오른쪽(동), 왼쪽(서), 아래(남), 위(북) 중 한 방향을 바라볼 수 있다.
로봇의 이동을 제어하는 명령어는 다음과 같이 세 가지이다.
* L: 로봇이 왼쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
* R: 로봇이 오른쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
* A: 로봇이 바라보는 방향으로 두 칸 전진한다. 단, 이 과정에서 로봇이 격자판 바깥을 나간다면 로봇은 이 명령을 수행할 수 없다.
당신의 사수는 로봇 사용법을 시연해 주고자, 격자판 어딘가에 로봇을 두고 명령어를 입력해 가며 로봇을 움직였다. 이 때, 사수는 로봇이 같은 칸을 두 번 이상 방문하지 않도록 명령을 내렸고, 로봇이 방문한 모든 칸 (출발 칸 포함)을 지도에 표시하였다. 당신은 다음 날 출근해서 사수가 한 것처럼 로봇에 명령을 내려봐야겠다고 생각하며 퇴근하였다.
다음 날 출근한 당신은 사수가 넘겨준 지도를 보고 로봇이 어떤 칸들에 방문하였는지를 정확히 알 수 있었지만, 사수가 로봇에 어떤 명령을 내렸는지는 알 수 없었다. 당신은 오늘 로봇이 지도에 사수가 표시한 모든 칸들만을 방문하도록 로봇을 조작하고자 하며, 이를 위해 아래 정보를 계산해 주는 프로그램을 작성하려고 한다.
1. 처음 로봇을 어떤 칸에, 어떤 방향(동서남북 중 하나)으로 두어야 하는가?
2. 이후 로봇에 어떤 명령어를 어떤 순서대로 입력해야 하는가?
명령어를 입력하는 일은 번거롭기 때문에, 당신은 입력할 명령어의 개수를 최소화해야 한다. 처음 로봇을 어디에, 어느 방향으로 놓는지에 따라서도 필요한 명령어 개수가 달라질 수 있음에 유의하라.
* 5 ≤ H, W ≤ 25
* 사수는 한 번 이상의 A 명령을 내렸다. 따라서, 로봇이 방문한 칸 수는 최소 3개 이상이다.
이 문제의 경우 목표를 달성할 수 있는 방안이 여러개 일 수 있으며 그 중 아무 것이나 출력해도 답으로 처리된다.
아래의 입출력 예제를 보면, 하나의 입력에 대해 각각 달성할 수 있는 방안(출력)이 2개씩 존재한다. [예제 1, 예제 2], [예제 3, 예제 4] 두 가지 방안 중 하나가 정답으로 출력된 경우 정답으로 인정된다.
첫 번째 줄에 격자판의 세로 크기 H와 가로 크기 W가 공백 하나를 사이로 두고 주어진다. 다음에는 사수가 넘겨준 지도가 주어진다. H개의 줄에 W개의 문자가 주어지는데, 이 중 i(1 ≤ i ≤ H)번째 줄의 j(1 ≤ j ≤ W)번째 문자는, 사수가 조작한 로봇이 i행 j열을 방문했다면 '#'이고, 방문하지 않았다면 '.'이다.
첫 번째 줄에 두 개의 정수 a(1 ≤ a ≤ H)와 b(1 ≤ b ≤ W)를 공백 하나씩을 사이로 두고 출력한다. 이는 처음 로봇을 격자판의 a행 b열에 두어야 함을 의미한다.
두 번째 줄에 '>', '<', 'v', '^' (따옴표 제외) 중 하나를 출력한다. 이 문자는 처음 로봇이 바라보는 방향을 의미하며, >는 동쪽, <는 서쪽, v는 남쪽, ^는 북쪽이다.
세 번째 줄에 당신이 로봇에 내려야 하는 명령어들을 공백 없이 명령을 내릴 순서대로 출력한다. 이 문자열의 길이가 곧 당신이 내리는 명령어의 개수이며, 명령어의 개수를 최소화해야 정답 처리된다.
명령어의 개수를 최소화하면서 목표를 달성할 수 있는 방법이 여러 가지라면, 그 중 한 가지를 아무거나 출력하면 된다.
문제 요점
로봇에게 가능한 명령: L: 왼쪽90도회전, R: 오른쪽90도회전, A:두 칸 전진 (단 바깥으로 나가면 수행안함)
지도상에 방문했음 # 아님. 로 표시
왔던 길을 다시 방문할 수 없음
방법은 여러가지가 있는데 한가지만 출력해도 된다.
첫째줄에 로봇의 시작점, 두번째 줄에 첫번째 방향, 세번째 줄에 전체 명령어를 출력해라
풀이
재방문 못 함 => 겹치지 않는 하나의 경로 => bfs 를 통해 하나의 경로를 파고드는 것을 생각했다.
로봇은 두칸씩 이동하므로 서로 다른 선이 바로 인접하는 경우는 없다
시작점 찾기
먼저 한 경로의 시작점이나 끝점을 찾은 뒤 경로를 파고들어야함
=> 전체를 순회하며 #를 만났을 때 오직 한 방향만 갈 수 있는 점이 바로 시작점이나 끝점임을 이용하여 찾는다
시작점을 찾으면 해당 위치를 이미 방문한 곳으로 표시하고 큐에 삽입하여 다음 경로를 찾는다
이때 현재 위치와 기존의 방향도 같이 기록한다. (나중에 방향 전환할때 판단하기 위해서이다)
const queue = [{r: startPoints.r, c: startPoints.c, prevDir: undefined }];
현재위치에서 상하좌우를 탐색하며 유일하게 연결된 #를 찾으면 (이동할 방향을 찾음)
totalRoute에 방향전환의 명령어를 추가하고 현재방향으로 변경한 뒤
그 방향대로 배열을 넘어가거나 .가 나오기 전까지 쭉 직진한다 (이동하면서 방문한 곳은 . 로 방문함을 표시한다.)
직진하기
한칸 씩 직진할 때마다 step++하여 다음 방향으로 전환하기 전까지 몇번의 step을 움직였는지 기록하고
방향을 전환할 때가 오면
totalRoute에 step/2만큼 A를 추가하고
queue에 새로운 현재의 위치와 현재의 방향을 push해준다.
이런식으로 queue.length가 존재할 때까지 순회하며 totalRoute를 만들어나간다.
R, L 판단하기
방향전환시 R, L인지를 쉽게 파악하기 위해
북동남서는 각각 0123로 표기하였고, 아래와 같이 전환 할 수 있는 경우의 obj를 만들어서
turnObj[전 방향][현재 방향]이 존재하면 R, 아니면 L 로 방향전환을 판단했다.
const turnObj = {
0: {1: 'R'},
1: {2: 'R'},
2: {3: 'R'},
3: {0: 'R'},
}
전체코드
const readline = require('readline');
const rl = readline.createInterface({
input : process.stdin,
output : process.stdout
});
const lines = [];
// input
rl.on('line', input => {
lines.push(input.split(' ').map(e => {
if (!isNaN(e)) return parseInt(e);
return e;
}))
})
rl.on('close', () => {
const [h, w] = lines.shift();
const map = lines.map(e => e[0].split(''));
const dirObj = {0: '^', 1: '>', 2: 'v', 3: '<'};
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
let startPoints = {};
function isInsideArr(r, c) {
return r >= 0 && r < h && c >= 0 && c < w;
}
// 시작점 찾기
let founded = false;
for (let r = 0; r < h; r++) {
for (let c = 0; c < w; c++) {
if (map[r][c] === '#') {
let connectedCount = 0;
for (let i = 0; i < 4; i++) {
const nextR = r + dr[i];
const nextC = c + dc[i];
if (isInsideArr(nextR, nextC) && map[nextR][nextC] === '#') {
connectedCount++;
}
}
// 시작점을 찾음
if (connectedCount === 1) {
console.log(`${r+1} ${c+1}`)
startPoints = {r, c}
founded = true;
break;
}
}
}
if (founded) break;
}
// 경로를 따라 이동
map[startPoints.r][startPoints.c] = '.'; // 방문표시;
const queue = [{r: startPoints.r, c: startPoints.c, prevDir: undefined }];
const turnObj = {
0: {1: 'R'},
1: {2: 'R'},
2: {3: 'R'},
3: {0: 'R'},
}
// 경로를 따라가며 방향을 기록한다
let totalRoute = [];
while(queue.length) {
const {r, c, prevDir} = queue.shift();
for (let i = 0; i < 4; i++) {
let nextR = r + dr[i];
let nextC = c + dc[i];
// 현재 위치에서 이동할 방향 찾음
if (isInsideArr(nextR, nextC) && map[nextR][nextC] === '#') {
const currDir = i;
// 방향추가
if (prevDir === undefined) {
totalRoute.push(currDir);
} else {
totalRoute.push(turnObj[prevDir][currDir] ? 'R' : 'L');
}
let step = 0;
// 방향을 찾으면 직진
while(isInsideArr(nextR, nextC) && map[nextR][nextC] === '#') {
map[nextR][nextC] = '.'; // 방문표시
step++;
nextR += dr[currDir];
nextC += dc[currDir];
}
nextR -= dr[currDir];
nextC -= dc[currDir];
const half = step/2;
for (let t = 0; t < half; t++) {
totalRoute.push('A')
}
queue.push({r: nextR, c: nextC, prevDir: currDir})
}
}
}
const firstDir = totalRoute.splice(0, 1)[0];
console.log(dirObj[firstDir]);
console.log(totalRoute.join(''));
process.exit();
})
