백준 BOJ 16174- 점프왕 쩰리 (Large & Small)

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

16173번: 점프왕 쩰리 (Small)

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

16174번: 점프왕 쩰리 (Large)

BFS 문제.

bfs를 함에 있어서 위치에 따라 이동거리가 바뀐다는 점에 유의해서 작성해주면 문제를 해결할 수 있다.

입력 범위가 작은 Small 문제는 브루트포스도 가능하고,

Large 문제는 BFS를 사용해야 한다.

 

이동거리가 곧 현재 위치에서의 배열 입력값이므로,

이동 방향을 나타내주는 dx[i] 에 현 위치인 arr[x][y]를 곱해주면 된다.

즉, (x,y) 에서 갈수 있는 점인 (nx,ny)의 목록을

int nx = x + dx[i]*arr[x][y];
int ny = y + dy[i]*arr[x][y];

로 구할 수 있다.

(nx,ny) 가 격자판 범위 밖으로 넘어가지 않도록 유의할것.

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

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

int n;
int arr[123][123] = {0};
int vis[123][123] = {0};

void bfs(int a, int b){
	memset(vis, 0, sizeof(vis));
	queue<pair<int,int>> q;
	q.push({a,b});
	vis[a][b] = 1;
	
	while(!q.empty()){
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		
		for(int i=0; i<2; i++){
			int nx = x + dx[i]*arr[x][y];
			int ny = y + dy[i]*arr[x][y];
			
			if(!(1<=nx && nx<=n) || !(1<=ny && ny<=n)) continue;
			
			if(vis[nx][ny] != 1){
				vis[nx][ny] = 1;
				q.push({nx,ny});
			}
		}
	}
}

int main(){
	cin >> n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >> arr[i][j];
		}
	}
	
	bfs(1,1);
	
	if(vis[n][n] == 0) cout << "Hing";
	else cout << "HaruHaru";
}

Large / Small 둘다 AC를 받는 소스코드이다.