[백준] 16173번 : 점프왕 쩰리 (Small)

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 BFS 방식으로 풀었다.

1) 각 칸에 대한 (y좌표, x좌표, 칸의 수)를 저장하는 tuple들을 저장하는 큐를 선언한다.
2) 출발칸에 대해 방문 처리 후 큐에 삽입한다.
3) 큐의 최전방 노드를 삭제하고, 이에 저장된 칸과 인접한 칸들을 전부 큐에 삽입한다. 단, 해당 문제에서는 오른쪽과 아래로만 이동 가능하기 때문에 인접 칸 중 위와 왼쪽은 배제한다. 또한 이동할 때 한 칸씩이 아닌 현재 칸에 적힌 수 만큼만 이동 가능함에 유의한다.
4) 인접 칸을 큐에 삽입할 때, 인접 칸의 값을 확인해 -1 이면 'HaruHaru'를 출력 후 바로 return한다.
5) 3) ~ 4)를 반복하고, 큐가 빌 때까지 'HaruHaru'가 출력되지 않았다면 마지막에 'Hing'이 출력된다.

❗문제를 잘 읽어보면 칸에 0 ~ 100의 숫자가 적히므로, 0이 올 경우 어떤 칸으로도 이동할 수 없기 때문에 곧바로 Hing을 출력하고 return하면 된다. (이 부분을 빼먹어서 메모리 초과 발생했음..)

🖥️ 풀이 코드

#include <bits/stdc++.h>

using namespace std;

void BFS(int n, vector<tuple<int, int, int>> arr)
{
	queue<tuple<int, int, int>> q;

	q.push(arr[0]);		// 가장 첫 칸에 대한 데이터 큐에 삽입

	while (!q.empty())
	{
		// 최전방 노드에 저장된 데이터들을 변수로 저장 후 큐에서 삭제
		int y = get<0>(q.front());	// y좌표
		int x = get<1>(q.front());	// x좌표
		int value = get<2>(q.front());	// 칸의 값
		q.pop();

		// 칸의 값이 0이면 더 이상 이동 불가능 (문제 잘 읽을 것!)
		if (value == 0)	
		{
			cout << "Hing";
			return;
		}
			
		// 오른쪽으로 이동하는 경우 : (현재 x 좌표 + 칸의 값 < n) 일 때 이동 가능.)
		if (x + value < n)
		{
			q.push(arr[y * n + x + value]);		// arr 벡터에 접근할 때는 y 좌표에 n을 곱해주어야 함. -> (1, 0) 좌표의 칸은 arr[3]에 저장

			if (get<2>(arr[y * n + x + value]) == -1)	// 목표 칸에 도착하면 HaruHaru 출력
			{
				cout << "HaruHaru";
				return;
			}
		}

		// 아래로 이동하는 경우 : (현재 y 좌표 + 칸의 값 < n) 일 때 이동 가능
		if (y + value < n)
		{
			q.push(arr[(y + value) * n + x]);

			if (get<2>(arr[(y + value) * n + x]) == -1)
			{
				cout << "HaruHaru";
				return;
			}
		}
	}
	cout << "Hing";		// 큐가 비워질 때까지 도착 못하면 도착 지점 도달 불가능
}

int main()
{	
	int n; 
	cin >> n;
	cin.ignore();

	vector<tuple<int, int, int>> arr(n * n);	// 각 칸에 대해 (y좌표, x좌표, 칸의 값) 저장 (arr[0] = (0, 0), arr[1] = (0, 1), ... , arr[3] = (1, 0), arr[4] = (1, 1), ... 과 같은 순서)

	// 맵 입력하기
	for (int i = 0; i < n; i++)
	{
		string input;
		getline(cin, input);

		istringstream ss(input);
		string stringBuffer;

		int j = 0;
		while (getline(ss, stringBuffer, ' '))
		{
			arr[i * n + j] = tuple<int, int, int>(i, j, stoi(stringBuffer));
			j++;
		}
	}
	BFS(n, arr);
}