문제
https://school.programmers.co.kr/learn/courses/30/lessons/49994
접근
게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하는 문제이다.
- 그래프탐색
- 중복배열체크 -> 중복에 있다면 바로 그때까지의 결과 return
- 주의사항: 그래프를 벗어나는 이동은 무시한다.
- 그래프의 크기는 10*10 정사각형이다.
https://developerm.tistory.com/196
[Programmers/JS] 방문 길이 / 프로그래머스 코딩 테스트 연습
방문 길이 문제 설명 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한
developerm.tistory.com
check 배열 쓰는 방식을 굉장히 특이하게 하는 문제더라.
풀이
function solution(input) {
const dirs = input.split("");
const visited = new Set();
const pos = { x: 0, y: 0 };
for (const dir of dirs) {
const prevPos = {
x: pos.x,
y: pos.y,
};
if (dir === "U" && pos.y < 5) pos.y += 1;
if (dir === "D" && pos.y > -5) pos.y -= 1;
if (dir === "R" && pos.x < 5) pos.x += 1;
if (dir === "L" && pos.x > -5) pos.x -= 1;
const move1 = prevPos.x + "" + prevPos.y + pos.x + pos.y;
const move2 = pos.x + "" + pos.y + prevPos.x + prevPos.y;
if (move1 != move2 && !visited.has(move1) && !visited.has(move2)) {
visited.add(move1);
visited.add(move2);
}
}
return visited.size / 2;
}
* 마지막에 둘 다 넣어주는 이유:
(0,0) -> (1,2) 를 지나갔다고 치자. 돌고 돌다보니 다시 (1,0) 지점으로 왔다. 그리고 다시 (1,0) 에서 (0,0) 가는 형태였다.
이경우 이 길은 지나갔기 때문에 탐색을 멈추고 결과를 도출해야 한다.
(0,0) -> (1,0)
(1,0) -> (0,0)
를 visited 가 두 경로를 모두 가지고 있지 않으면 아직 방문하지 않은 새로운 경로로 착각해 또 경로 수를 카운팅한다.
'Board > 알고리즘' 카테고리의 다른 글
백준 1463 자바스크립트 (0) | 2023.02.15 |
---|---|
백준 10026 자바스크립트 (0) | 2023.02.13 |
프로그래머스 멀쩡한 사각형 (0) | 2023.02.10 |
프로그래머스 예산 (0) | 2023.02.10 |
프로그래머스 소수 만들기 (0) | 2023.02.10 |