백준 16173. 점프왕 쩰리(Small)(JAVA)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
		int[][] gameArea = new int[a][a];
		boolean[][] visited = new boolean[a][a];
		
		for(int i = 0 ; i < gameArea.length ; i++) {
			for(int j = 0 ; j < gameArea.length; j++) {
				gameArea[i][j] = sc.nextInt();
				visited[i][j] = false;
			}
		}
		BFS(gameArea, visited);
		sc.close();
	}
	
	static void BFS(int[][] gameArea, boolean[][] visited) {
		
		int leng = gameArea.length;
		boolean result = false;
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {0,0});
		
		while(!q.isEmpty()) {
			int[] now = q.poll(); // now에 (0,0)이 들어감. now배열에 {0,0}이 들어간 것. 
			int row = now[0]; // 0 
			int col = now[1]; // 0 
			
			visited[row][col] = true;
			
			if(gameArea[row][col] == -1) {
				result = true;
				break;
			}
			
			int bottom = row + gameArea[row][col];
			int right = col + gameArea[row][col];
			
			if(bottom < leng && !visited[bottom][col]) {
				q.add(new int[] {row + gameArea[row][col], col});
				visited[bottom][col] = true;
			}
			if(right < leng && !visited[row][right]) {
				q.add(new int[] {row, col+gameArea[row][col]});
				visited[row][right] = true;
			}
			
		}
			if(result) {
				System.out.println("HaruHaru");
			}else {
				System.out.println("Hing");
			}
			
		}
	}

○ 문제 요약

문제를 간단하게 설명하면 3 X 3 게임판에서 (1,1)을 시작 좌표로 하여 현재 좌표에 있는 숫자만큼 오른쪽이나 아래로 이동하여 (3,3) 좌표로 이동할 수 있으면 "HaruHaru"를 출력하고 그렇지 않으면 "Hing"을 출력한다.

○ 문제 풀이

int a : 게임 구역의 크기

int [][] gameArea : 게임 구역을 만들기 위한 2차원 배열

boolean [][] visited : 해당 좌표에 도착했다는 표시를 하기 위한 2차원 배열

문제를 풀기 위하여 BFS(너비 우선 탐색)을 사용했다. 

int leng : 해당 좌표에 있는 숫자에 맞게 오른쪽이나 아래로 이동할 경우 게임 구역을 벗어나는지 확인을 하기 위해 선언

boolean result : -1 값이 있는 좌표에 도착했을 때, result를 true로 설정하기 위해 선언

Queue : BFS 탐색을 하기 위해 Queue를 사용

q.add(new int [] {0,0}) : 미리 만든 q에 (0,0)을 넣음   

while문은 q에 아무것도 없을 때까지 수행하도록 한다.

처음 now배열에는 q에 넣은 (0,0)를 빼서 넣어주면 now [2] = {0,0}이 되고 int row에는 0이 들어가고

int col에도 0이 들어간다.

그래서 visited [0][0]은 시작 좌표를 의미하고 시작 좌표에서 시작하기 때문에 true를 넣어줘 방문했다는 것을 알린다.

if문에서는 현재 있는 좌표의 값이 -1이면 성공적으로 이동했다는 것이므로 result에 true를 넣어주고 while문을 빠져나간다.

int bottom = 0 + gameArea [0][0]; // 1 = 0 + 1 

int right = 0 + gameArea [0][0]; // 1 = 0 + 1

---

여기서 if문이 성립한다는 것은 해당 좌표에서 해당 좌표에 있는 값만큼 아래나 오른쪽으로 이동해도 게임 구역을 이탈하지 않는다는 것을 의미한다. 

 

- 해당 좌표에서 해당 좌표의 값만큼 아래로 이동할 경우 

if(1 < 3 && false){ // visited [1][0]은 방문한 적 없기 때문에 false이다.

 q.add(new int [] { 0 + 1, 0});  // gameArea [1][0]로 이동한 것을 Queue에 넣어 증명한다. 

 visited [1][0] = true; // gamaArea [1][0]에 이동했으므로 visited [1][0]에 true를 넣어 방문했음을 알려준다.

}

 

- 해당 좌표에서 해당 좌표의 값만큼 오른쪽으로 이동할 경우 

if(1 < 3 && false){ // visited [0][1]은 방문한 적 없기 때문에 false이다.

 q.add(new int [] { 0, 0 +1});  // gameArea [0][1]로 이동한 것을 Queue에 넣어 증명한다. 

 visited [0][1] = true; // gamaArea [0][1]에 이동했으므로 visited [0][1]에 true를 넣어 방문했음을 알려준다.

}

gamaArea [row][col] == -1이 될 때까지 while문을 수행하고 result에 true를 넣어주고 while문을 빠져나온다.

while문을 빠져나오고 if문의 조건문에서 result가 true이면 "HaruHaru"를 출력해주고 false이면 "Hing"을 출력해줌으로써 문제를 마무리한다. 

○ 결과

○ 평가​

BFS를 공부하기 위해 이 문제를 시작했을 때, 너무 막막해서 다른 분들의 코드를 보고 분석하면서 나름대로 공부가 되었다.

지금은 다른 분들의 코드를 보면서 공부를 하는 입장이지만 좀 더 노력해서 다른 분들에게 도움이 되는 사람이 되고 싶다.

이 문제를 풀면서 내 스스로 문제를 풀지 못했다는 실망보다는 앞으로 BFS 나아가 DFS를 스스로 구현하는 밑거름이라고 긍정적으로 생각하고 공부를 해나가자.