반응형
‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.
- ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
- ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
- ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
- ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
- ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.
새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!
입력
입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.
입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.
게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.
출력
‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.
예제 입력 1 복사
3
1 1 10
1 5 1
2 2 -1
예제 출력 1 복사
HaruHaru
쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다.
예제 입력 2 복사
3
2 2 1
2 2 2
1 2 -1
예제 출력 2 복사
Hing
쩰리는 맨 왼쪽 위의 칸에서 출발하더라도 절대 게임의 승리 지점인 (3, 3)에 도달할 수 없다.
문제 풀이 힌트
bfs를 활용한 코드를 작성하기로 한다.
문제 풀이 코드
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input.shift());
const board = input.map(v => v.split(' ').map(v => +v));
const visited = Array.from({length:N}, ()=> new Array(N).fill(false)); //board를 방문했는지 확인
let queue = [];
queue.push([0,0]); //시작이 0,0이라고 함
visited[0][0] = true; //방문 체크
let answer = 'Hing' //만약 -1이 적혀있는 칸에 도착하면 'HaruHaru' 로 바꿀 것임.
while(queue.length > 0){ //q에 요소가 있을 때까지
let [y,x] = queue.shift(); //맨 앞 요소 빼기
let v = board[y][x]; //해당 칸의 숫자 확인하기
if(v === -1){ //칸이 -1이라면,
answer = 'HaruHaru'
break;
}else{ //칸이 -1이 아니라면
if(y + v < N && !visited[y+v][x]){ //board를 넘어가지 않고, 방문하지 않았을 때
visited[y+v][x] = true; //방문 체크
queue.push([y+v, x]);//아래로 이동
}
if(x + v < N && !visited[y][x+v]){ //board를 넘어가지 않고, 방문하지 않았을 때
visited[y][x+v] = true; //방문 체크
queue.push([y, x+v]);// 오른쪽으로 이동
}
}
}
console.log(answer);
Only 풀이 코드
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input.shift());
const board = input.map(v => v.split(' ').map(v => +v));
const visited = Array.from({length:N}, ()=> new Array(N).fill(false));
let queue = [];
queue.push([0,0]);
visited[0][0] = true;
let answer = 'Hing'
while(queue.length > 0){
let [y,x] = queue.shift();
let v = board[y][x];
if(v === -1){
answer = 'HaruHaru'
break;
}else{
if(y + v < N && !visited[y+v][x]){
visited[y+v][x] = true;
queue.push([y+v, x]);
}
if(x + v < N && !visited[y][x+v]){
visited[y][x+v] = true;
queue.push([y, x+v]);
}
}
}
console.log(answer);
반응형
'알고리즘 문제 풀기' 카테고리의 다른 글
백준 10974: 모든 순열 - javascript(완전탐색) (0) | 2024.02.13 |
---|---|
백준 1213: 팰린드롬 만들기 - javascript(구현) (0) | 2024.02.12 |
백준 1388: 바닥 장식 - javascript(이중 for문, dfs) (1) | 2024.02.08 |
백준 1388: 바닥 장식 - javascript(이중 for문, dfs) (1) | 2024.02.07 |
백준 10610: 30 - javascript(그리디) (0) | 2024.02.06 |