[Baekjoon] 16174_점프왕 쩰리 (Large)

Silver I

문제(출처: https://www.acmicpc.net/problem/16174)

---

< 점프왕 쩰리 (Large) >

 

문제 풀이

 

bfs로 문제를 해결하였다. 

 

 

 - my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _16174_ {
	static int dx[]= {0,1}; // 아래, 오른쪽
	static int dy[]= {1,0};
	static int arr[][], n;
	static boolean flag;

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 게임 구역의 크기
		n=Integer.parseInt(bf.readLine());
		
		// 게임판의 구역
		arr=new int[n][n];
		for(int i=0; i<n; i++) {
			st=new StringTokenizer(bf.readLine());
			for(int j=0; j<n; j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		flag=false;
		search(0,0);
		if(flag) System.out.println("HaruHaru");
		else System.out.println("Hing");
	}

	private static void search(int i, int j) {
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int[] {i,j});
		
		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			int cnt=arr[temp[0]][temp[1]];
			for(int k=0; k<2; k++) {
				// 이동
				int x=temp[0]+(dx[k]*cnt);
				int y=temp[1]+(dy[k]*cnt);
				if(x>=0 && x<n && y>=0 && y<n ) {
					// 끝 점인 경우 종료
					if(x==n-1 && y==n-1) { 
						flag=true;
						break;
					}
					queue.add(new int[] {x,y});
				}
			}
			if(flag) {
				break;
			}
		}
	}
}

 

Main

- 게임 구역의 크기 (n) 입력

- 게임판의 구역 입력

- bfs 탐색 후 끝 점에 도달할 수 있으면 "HaruHaru", 없으면 "Hing"을 출력

 

search

- queue가 빌 때까지 반복하여 이동할 수 있는 칸만큼 아래로, 오른쪽으로 이동하여 게임 구역의 범위 안이며,

아직 방문하지 않은 곳이면 queue에 추가

- 끝 점에 도달할 경우 바로 종료

 

---

생각🤔

 

처음에 이동할 수 있는 칸만큼 이동할 때, 당연히 오른쪽 아래 섞어서 이동할 수 있는 줄 알고

예제부터 한참본 문제...

 

---