1. 문제
로보틱스 분야는 현대자동차그룹의 미래 성장동력인 5대 신사업 중 하나이다.
현대자동차그룹에 입사하여 로봇 연구 개발 부서에 막 입사한 당신은 아래와 같은 기능을 하는 간단한 로봇의 사용법을 전달받았다. 로봇은 H행 W열의 2차원 격자판 위를 돌아다닌다. 격자판의 각 칸은 정사각형 모양이며, 로봇은 격자판의 칸 하나를 차지한다. 로봇은 오른쪽(동), 왼쪽(서), 아래(남), 위(북) 중 한 방향을 바라볼 수 있다.
로봇의 이동을 제어하는 명령어는 다음과 같이 세 가지이다.
- L: 로봇이 왼쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
- R: 로봇이 오른쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
- A: 로봇이 바라보는 방향으로 두 칸 전진한다. 단, 이 과정에서 로봇이 격자판 바깥을 나간다면 로봇은 이 명령을 수행할 수 없다.
당신의 사수는 로봇 사용법을 시연해 주고자, 격자판 어딘가에 로봇을 두고 명령어를 입력해 가며 로봇을 움직였다. 이 때, 사수는 로봇이 같은 칸을 두 번 이상 방문하지 않도록 명령을 내렸고, 로봇이 방문한 모든 칸 (출발 칸 포함)을 지도에 표시하였다. 당신은 다음 날 출근해서 사수가 한 것처럼 로봇에 명령을 내려봐야겠다고 생각하며 퇴근하였다.
다음 날 출근한 당신은 사수가 넘겨준 지도를 보고 로봇이 어떤 칸들에 방문하였는지를 정확히 알 수 있었지만, 사수가 로봇에 어떤 명령을 내렸는지는 알 수 없었다. 당신은 오늘 로봇이 지도에 사수가 표시한 모든 칸들만을 방문하도록 로봇을 조작하고자 하며, 이를 위해 아래 정보를 계산해 주는 프로그램을 작성하려고 한다.
- 처음 로봇을 어떤 칸에, 어떤 방향(동서남북 중 하나)으로 두어야 하는가?
- 이후 로봇에 어떤 명령어를 어떤 순서대로 입력해야 하는가?
명령어를 입력하는 일은 번거롭기 때문에, 당신은 입력할 명령어의 개수를 최소화해야 한다. 처음 로봇을 어디에, 어느 방향으로 놓는지에 따라서도 필요한 명령어 개수가 달라질 수 있음에 유의하라.
제약조건
- 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는 남쪽, ^는 북쪽이다.
세 번째 줄에 당신이 로봇에 내려야 하는 명령어들을 공백 없이 명령을 내릴 순서대로 출력한다. 이 문자열의 길이가 곧 당신이 내리는 명령어의 개수이며, 명령어의 개수를 최소화해야 정답 처리된다.
명령어의 개수를 최소화하면서 목표를 달성할 수 있는 방법이 여러 가지라면, 그 중 한 가지를 아무거나 출력하면 된다.
입력예제1
5 8
#######.
........
........
........
........출력예제1
1 7
<
AAA입력예제2
5 8
#######.
........
........
........
........출력예제2
1 1
>
AAA입력예제3
9 14
.......###....
.........#....
.#####...###..
.#.........#..
.#.#####...###
.#.#...#.....#
.###.###.....#
.....#.......#
.....#########출력예제3
3 6
<
AALAALALARAARARALALAAAALAALARALARALA입력예제4
9 14
.......###....
.........#....
.#####...###..
.#.........#..
.#.#####...###
.#.#...#.....#
.###.###.....#
.....#.......#
.....#########출력예제4
1 8
>
ARALARALARAARAAAARARALALAALARARAARAA2. 풀이
이 문제에서 해야 할 일은 다음과 같다.
- 격자판에서 로봇이 방문한 칸을 찾아서 시작점인지 체크하기
- 시작점의 x좌표, y좌표, 처음 로봇이 바라보는 방향을 저장
- 시작점에서부터 방문했던 칸을 따라가면서 지나온 곳은
.으로 표시하고,A,L,R명령어 업데이트하기 - 모든 칸을 방문했다면 중단하고, 출력결과 반환하기
시작점을 찾는 게 중요하다고 생각해서 시작점을 찾는 함수(checkStart)를 따로 만들었다.
시작점의 특징은 # 표시로 되어 있으면서 해당 칸 기준 동서남북으로 위치한 칸 중 #표시가 한 개만 있어야 한다는 것이다.
해당 칸을 찾으면 시작점의 좌표와 방향을 반환한다.
시작점에서부터 끝점까지 명령어를 업데이트하는 작업은 현재 칸에서 #이 있는 방향으로 첫 번째, 두 번째 칸이 #라면 지나온 자리를 모두 .으로 만들고 현재 칸 좌표를 새로 업데이트해 주면 된다.
이동할 수 없다면 회전을 해서 방향을 틀어야 하므로 동서남북 중 # 표시를 찾고, 찾았다면 회전한 명령어를 업데이트한다. 방향을 찾아도 #가 없다면 모든 경로를 방문했으므로 탈출한다.
전체 코드는 아래와 같다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let lines = [];
const wx = [-1, 0, 1, 0];
const wy = [0, 1, 0, -1];
const arrow = ["^", ">", "v", "<"];
let way = 0;
// 시작점 찾기 & 방향 찾기
function checkStart(board, height, width) {
for (let i = 0; i < height; i++) {
for (let j = 0; j < width; j++) {
if (board[i][j] === "#") {
let visited_cnt = 0;
for (let k = 0; k < 4; k++) {
let nx = i + wx[k],
ny = j + wy[k];
if (
nx >= 0 &&
nx < height &&
ny >= 0 &&
ny < width &&
board[nx][ny] === "#"
) {
visited_cnt++;
way += k;
}
}
if (visited_cnt === 1) {
return [i, j, way];
} else way = 0;
}
}
}
}
rl.on("line", (line) => {
lines.push(line);
}).on("close", () => {
const [height, width] = lines[0].split(" ").map(Number);
let board = lines.slice(1).map((e) => e.split(""));
let command = "";
// 시작점 찾기 & 처름 로봇이 바라보는 방향 찾기
let [start_x, start_y, start_idx] = checkStart(board, height, width);
let current_x = start_x;
let current_y = start_y;
let idx = start_idx;
// 경로찾아서 좌표 옮기기 & 지나온 곳 .으로 만들기
while (true) {
let moved = false;
// A 명령어 처리 (앞으로 2칸 전진)
if (
current_x + wx[idx] * 2 >= 0 &&
current_x + wx[idx] * 2 < height &&
current_y + wy[idx] * 2 >= 0 &&
current_y + wy[idx] * 2 < width &&
board[current_x + wx[idx]][current_y + wy[idx]] === "#" &&
board[current_x + wx[idx] * 2][current_y + wy[idx] * 2] === "#"
) {
command += "A";
board[current_x][current_y] = ".";
board[current_x + wx[idx]][current_y + wy[idx]] = ".";
current_x += wx[idx] * 2;
current_y += wy[idx] * 2;
moved = true;
}
// 두 칸 전진할 수 없다면 회전이 필요하다는 의미이므로 L 또는 R 명령어 처리
if (!moved) {
let found_direction = false;
for (let i = 0; i <= 3; i++) {
let next_way_idx = (idx + i) % 4;
if (
current_x + wx[next_way_idx] >= 0 &&
current_x + wx[next_way_idx] < height &&
current_y + wy[next_way_idx] >= 0 &&
current_y + wy[next_way_idx] < width &&
board[current_x + wx[next_way_idx]][current_y + wy[next_way_idx]] ===
"#"
) {
found_direction = true;
command += i === 1 ? "R" : i === 3 ? "L" : "RR";
idx = next_way_idx;
break;
}
}
if (!found_direction) break; // 모든 경로 방문했다면 루프 종료
}
}
// 출력하기
console.log(start_x + 1, start_y + 1);
console.log(arrow[start_idx]);
console.log(command);
process.exit();
});모든 케이스를 통과해서 문제를 해결했지만 이 코드보다 더효율적으로 작성할 수 있을 것 같긴 하다.
격자판에서 칸을 옮기는 작업을 함수로 따로 빼도 괜찮을듯 싶다.
나중에 이 문제를 다시 푼다면 풀이를 다르게 해서 풀어봐야지.
