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

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

---

문제

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

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

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

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

---

입력

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

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

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

---

출력

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

---

예제 입력, 출력

---

알고리즘 분류

다이나믹 프로그래밍

그래프이론

그래프탐색

너비우선탐색

깊이우선탐색

---

해설

백준 16173 점프왕 쩰리(Small)의 메모리 개선을 요구하는 문제이다. 이전 문제에서는 N의 값이 2혹은 3이었지만 이 문제에서는 64까지 올라가기 때문에 이전 문제 코드를 그대로 제출하였을 때 메모리 초과가 발생할 수 있다.

 

메모리 문제를 해결하는 방법은 간단하다. 결국 해당 문제는 큐에 동일한 정점(좌표)들이 푸쉬되기 때문에 방문되었는지 여부를 체크하는 맵과 동일한 크기의 배열을 하나 더 선언하여 큐에 해당 정점이 한번만 큐에 들어가도록 개선할 수 있다.

 

또한 이전 문제에서 0인 발판을 밟았을 때를 예외상황으로 처리하여 루프를 방지했지만 개선된 코드에서는 방문했음 표시를 해버리기 때문에 예외처리를 따로 하지 않아도 자동으로 스킵된다.

 

---

소스코드

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

using namespace std;
int game[SIZE][SIZE]; // 맵의 상태를 저장할 2차원 배열
bool visited[SIZE][SIZE] = { 0, }; // 맵의 각 위치가 방문되었는지 저장하는 2차원 배열
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) { // 만약 루프가 발생되는 지점이라면
		//	continue; // 스킵
		//} 
		// x축과 평행하게 뛰는 경우
		int nx = x + game[x][y];
		if (nx < n && !visited[nx][y]) {// 착지 지점이 맵 안에 있고 방문되지 않은 경우
			q.push({ nx, y });
			visited[nx][y] = true; // 큐에 푸쉬된 좌표 방문 표시
		}

		// y축과 평행하게 뛰는 경우
		int ny = y + game[x][y];
		if (ny < n && !visited[x][ny]) { // 착지 지점이 맵 안에 있고 방문되지 않은 경우
			q.push({ x, ny });
			visited[x][ny] = true; // 큐에 표시된 좌표 방문 표시
		}

	}
}

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); // 1, 1부터 탐색 시작
	if (clear) { // 클리어!
		cout << "HaruHaru";
	}
	else { 
		cout << "Hing";
	}
}