[C++]백준(BOJ) 16173번 점프왕 쩰리(Small) 문제풀이

https://www.acmicpc.net/problem/16173

---

문제

‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.

‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.

• ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
• ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
• ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
• ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
• ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.

새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

---

입력

입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.

입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.

게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

---

출력

‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.

---

예제 입력, 출력

 

---

알고리즘 분류

구현

그래프 이론

브루트포스 알고리즘

그래프 탐색

너비우선탐색

깊이우선탐색

---

해설

N x N의 정사각형 구역에서 '쩰리'가 (1, 1) 부터 출발하여 오른쪽 맨 아래칸(N, N)에 도달할 수 있는지의 여부를 알아보는 문제이다. 해당 문제를 해결하기 위해서는 BFS, DFS 둘 중 아무것이나 활용하면 될 것으로 보인다.

코드의 대략적인 흐름은 다음과 같다.

 

1. 맵의 상태를 입력받아 game 2차원 배열에 저장.

 

2. 1,1 부터 BFS 수행(코드 상에서는 0, 0으로 간주하여 탐색)

 

3. 좌표의 값(game배열의 값)만큼 아래, 오른쪽 이동 각각 해보며 맵 안쪽에 착지하는 경우에만 큐에 푸쉬

 

4. 좌표의 값이 0인 것들은 그대로 진행 시 무한 루프에 빠지기때문에 continue

 

5. 종료지점(game배열의 값이 -1)을 만났다면 클리어로 간주 후 함수 종료

 

6. 함수가 종료된 후 clear 플랙의 값에 따라 결과 출력

 

Small 문제이기 때문에 N값이 2~3이기 사이에서 결정되어 방문 여부를 기록하는 배열을 구현하지 않고 무한루프를 발생시키는 0 발판에 대한 예외만 처리해 준다면 메모리 초과가 발생하지 않는다. Large 문제를 해결하고 싶거나, 메모리 최적화가 필요하다면 방문 여부를 체크하는 로직을 추가하여 중복된 좌표가 큐에 푸쉬되지 않게 코드를 개선하면 된다.

---

소스코드

#include <iostream>
#include <queue> 
#define SIZE 3 // 맵의 최대 크기

using namespace std;
int game[SIZE][SIZE]; // 맵의 상황 
int n = 0; // 맵의 크기
bool clear = false; // 쩰리가 끝 점에 도달했는지

queue<pair<int, int>> q; // 좌표 형태로 큐에 저장



void bfs(int x, int y) { // 인자로 전달받은 좌표부터 너비 우선 탐색을 수행하는 함수

	q.push({ x, y }); // 시작점을 큐에 푸쉬

	while (!q.empty()) { // 큐가 빌 때까지
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (game[x][y] == -1) { // 만약 종료지점이라면
			clear = true; // 클리어!
			return;
		}
		if (game[x][y] == 0) { // 0인 칸에서는 이동이 불가능하다..
			continue;
		}
		int nx = x + game[x][y]; // x축에 평행하게 뛰는 경우
		if (nx < n) { // 경기장 안에 착지하는 경우에만
			q.push({ nx, y }); // 큐에 푸쉬한다
		}

		int ny = y + game[x][y]; // y축에 평행하게 뛰는 경우
		if (ny < n) { // 경기장 안에 착지하는 경우에만
			q.push({ x, ny }); // 큐에 푸쉬한다
		}

	}
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> game[i][j]; // 맵 입력받음
		}
	}

	bfs(0, 0); // 0, 0부터 게임 시작
	if (clear) { // 클리어!
		cout << "HaruHaru";
	}
	else { // 실패
		cout << "Hing";
	}
}