백준 16174번 : 점프왕 쩰리 c++ bfs

 

 

bfs 문제이다.

오른쪽과 아래쪽으로만 이동이 가능하기 때문에 visited가 딱히 필요없을것이라고 생각했지만, 

visited 처리를 해주지 않는다면 결과값은 제대로 나오지만 '메모리 초과'가 난다.

 

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX = 3;
int n;
int map[MAX][MAX];
int visited[MAX][MAX];

int dx[2] = { 0,1 };
int dy[2] = { 1,0 };

int bfs(int x, int y) {
	queue<pair<int,int>> q;
	q.push(make_pair(x, y));
	visited[0][0] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		int move = map[x][y];
		visited[x][y] = 1;
		q.pop();

		for (int i = 0; i < 2; i++) {
			int nx = x + move * dx[i];
			int ny = y + move * dy[i];
			if (!visited[nx][ny]) {
				if (nx < n && ny < n) {
					if (map[nx][ny] == -1) {
						return 1;
					}
					q.push(make_pair(nx, ny));
					//visited[nx][ny] = 1;
				}

			}
		}
	}
	return 0;
}

int main(void) {

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	int result = bfs(0,0);

	if (result) {
		cout << "HaruHaru" << "\n";
	}
	else {
		cout << "Hing" << "\n";
	}
}