문제
지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다.
["방향 거리", "방향 거리" … ]
예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다.
주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다.
주어진 방향으로 이동 중 장애물을 만나는지 확인합니다.
위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다.
공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H - 1, W - 1) 입니다.
공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제약조건
- 3 ≤ park의 길이 ≤ 50
- 3 ≤ park[i]의 길이 ≤ 50
- park[i]는 다음 문자들로 이루어져 있으며 시작지점은 하나만 주어집니다.
- S : 시작 지점
- O : 이동 가능한 통로
- X : 장애물
- park는 직사각형 모양입니다.
- 1 ≤ routes의 길이 ≤ 50
- routes의 각 원소는 로봇 강아지가 수행할 명령어를 나타냅니다.
- 로봇 강아지는 routes의 첫 번째 원소부터 순서대로 명령을 수행합니다.
- routes의 원소는 "op n"과 같은 구조로 이루어져 있으며, op는 이동할 방향, n은 이동할 칸의 수를 의미합니다.
- op는 다음 네 가지중 하나로 이루어져 있습니다.
- N : 북쪽으로 주어진 칸만큼 이동합니다.
- S : 남쪽으로 주어진 칸만큼 이동합니다.
- W : 서쪽으로 주어진 칸만큼 이동합니다.
- E : 동쪽으로 주어진 칸만큼 이동합니다.
- 1 ≤ n ≤ 9
문제 해석
간단한 탐색 문제이다.
2차원 배열의 index를 위치값이라고 생각하고 routes 값에 따라 탐색하고 조건을 맞추면 되는 문제다.
예전에 BFS, DFS 문제를 많이 풀어서 익숙한 문제이다. 삼성 코테에서 이런식의 문제가 많이 나왔었다.
park의 길이를 N, park[i]의 길이를 M이라고할때 시간복잡도는 다음과 같다.
O(N x M) = O(50 x 50) = 0(2500)
얼마 안된다 ~ ㅎㅎ
풀이
풀이1
function findStartPoint(park) {
for (let y = 0; y < park.length; ++y) {
for (let x = 0; x < park[y].length; ++x) {
if (park[y][x] === "S") {
return [y, x];
}
}
}
}
function process(park, routes, S) {
// 시작점
let cur = S.map((s) => Number(s));
// 지도의 가로 세로 길이
const n = park.length;
const m = park[0].length;
// routes의 명령대로 탐색
for (let i = 0; i < routes.length; ++i) {
const route = routes[i].split(" ");
const dir = route[0];
// 방향에 따른 움직이는 좌표
const acc =
dir === "N"
? [-1, 0]
: dir === "E"
? [0, 1]
: dir === "W"
? [0, -1]
: [1, 0];
let move = Number(route[1]);
// 현재 좌표
let cy = cur[0];
let cx = cur[1];
// 다음 좌표
let ny = cy;
let nx = cx;
for (let j = 0; j < move; ++j) {
// 방향에 따라 한 칸씩 움직임
ny += acc[0];
nx += acc[1];
// 다음에 도달할 곳이 만약 지도의 범위이고, 움직일수 있는 곳이면
if (ny >= 0 && ny < n && nx >= 0 && nx < m && park[ny][nx] !== "X") {
// 강아지를 움직여준다.
cur = [ny, nx];
} else {
// 만약 도달할 수 없는 곳이면 현재 좌표로 초기화, 반복문 탈출
cur = [cy, cx];
break;
}
}
}
return cur;
}
function solution(park, routes) {
var answer = [];
answer = process(park, routes, findStartPoint(park));
return answer;
}
한방컷!
아직 자바스크립트 문법에 익숙하지가 않다... 배열 메소드, 문자열 메소드 ... 딱딱 떠올라야하는데
좀 더 줄여보자.
풀이 2
function solution(park, routes) {
var answer = [];
const n = park.length;
const m = park[0].length;
// route의 방향에 따라 계속 조건으로 처리하던 부분을 그냥 객체를 사용해서 접근하도록
const dy = { N: -1, E: 0, S: 1, W: 0 };
const dx = { N: 0, E: 1, S: 0, W: -1 };
// 배열의 findIndex 메소드를 사용하여 강아지 좌표 저장
let y = park.findIndex((y) => y.includes("S"));
let x = park[y].split("").findIndex((x) => x === "S");
// routes 순회
for (let route of routes) {
// split의 결과에 따른 구조분해할당
const [dir, len] = route.split(" ");
// 문자열이기때문에 number로 변환
let nlen = Number(len);
// 현재 좌표
let cy = y;
let cx = x;
// 다음 좌표
let ny;
let nx;
while (nlen--) {
// 방향에따라 한 칸씩 움직임
(ny = y + dy[dir]), (nx = x + dx[dir]);
if (ny >= 0 && ny < n && nx >= 0 && nx < m && park[ny][nx] !== "X") {
// 조건에 맞으면 다음좌표로 움직임
(y = ny), (x = nx);
} else {
// 조건에 맞지 않으면 처음 출발한 좌표로 초기화, 탈출
(y = cy), (x = cx);
break;
}
}
}
answer = [y, x];
return answer;
}
흠 .. 그냥 파이썬으이나 c++로 풀까도 생각했지만, 요즘 코테가 너무 케바케라 ... 프론트엔드 코테로 알고리즘이 나오는경우는 잘 없지만, 나온다면 javascript를 강제하는 곳도 있고, python으로 다시 푼다고해도 기억안나는게 많을거라 ... 그냥 javscript로 간다.
