(#16173 Java) 점프왕 쩰리 (Small)

 

 

전형적인 dfs 코드이다.

DFS/BFS 문제가 코테에서 가장 많이 나오는 문제 유형이라고 한다.

아직 문제를 풀어본 경험이 없어 문제를 풀기 전 유튜브에서 문제 유형들과 기본적인 기초들을 공부했는데, 기본적인 틀은 정해져있는 것 같았다. 문제를 보고 어떻게 구상해야할지 연습이 많이 필요할 것 같다.

 

 

문제 해결

 

먼저 정사각형의 구역에서 젤리가 움직인다고 하니 칸 수를 입력받을 N과 2차원 배열, dfs에서 필수적인 boolean 타입의 방문여부 배열을 선언해준다. 또한 젤리가 오른쪽과 아래 방향으로만 움직일 수 있다고 했으니 이를 위한 좌표 값들을 만들어주자.

static int N;
static int[][] arr;
static boolean[][] visited; //방문 여부
static int[] dx = {0, 1}; //오른쪽 이동
static int[] dy = {1, 0}; //아래로 이동

 

이제 main 함수로 들어가보자. 

N을 입력받고, N만큼 arr 배열과 visited 배열을 만들어준다.

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    N = in.nextInt();
    arr = new int[N][N];
    visited = new boolean[N][N];

 

 

그리고 N만큼 이중루프를 돌면서 좌표값들을 읽어오면 된다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        arr[i][j] = in.nextInt();
    }
}

 

 

그리고 dfs를 가장 왼쪽, 가장 위의 칸 0,0부터 호출해줄건데 dfs 함수를 만들어주자.

 

도착지점에는 항상 -1이 적혀있다고 했다.

-1을 만나면 "HaruHaru"를 출력하고 시스템을 종료하도록 하자

if (arr[i][j] == -1) { //-1이 쓰여 있으면(도착 지점에 도달 했으면)
    System.out.println("HaruHaru");
    System.exit(0);
}

 

 

그리고 for문을 돌아줄건데, 오른쪽과 아래, 두 가지로 이동할 수 있으므로 범위를 아래와 같이 잡아준다.

그리고 새로운 x,y 좌표를 생성해준다.

이 때 주의해야할 점이 새로만든 좌표가 범위를 벗어나면 안된다는 점이다.

만약 벗어나면 continue를 해준다.

이런 경우가 아니라면, visited를 true로 체크해주고 dfs를 호출해주면 된다.

for (int k = 0; k < 2; k++) { //오른쪽,아래 두 가지로 이동할 수 있으므로
    int x = i + dx[k] * arr[i][j], y = j + dy[k] * arr[i][j]; //새로운 x,y 좌표 생성
    if (x >= N || y >= N || visited[x][y]) //새로운 만든 좌표가 범위를 벗어나면 continue
        continue;

    visited[x][y] = true; //아니면 방문 여부를 true로 바꾸고 dfs 호출.
    dfs(x, y);
}

 

만약 탐색이 끝나도 -1에 도달하지 못하면 "Hing"을 출력한다.

dfs 함수는 우리가 따로 만들어준 것이므로 전체적인 코드의 순서는 아래와 같다.

 

최종 코드

 

package org.example.silver;

import java.util.Scanner;

public class Jelly {

    static int N;
    static int[][] arr;
    static boolean[][] visited; //방문 여부
    static int[] dx = {0, 1}; //오른쪽 이동
    static int[] dy = {1, 0}; //아래로 이동

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        N = in.nextInt();
        arr = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        dfs(0, 0);

        System.out.println("Hing"); //dfs 탐색이 끝나도 -1에 도달하지 못하면 "Hing" 출력
    }

    private static void dfs(int i, int j) {
        if (arr[i][j] == -1) { //-1이 쓰여 있으면(도착 지점에 도달 했으면)
            System.out.println("HaruHaru");
            System.exit(0);
        }

        for (int k = 0; k < 2; k++) { //오른쪽,아래 두 가지로 이동할 수 있으므로
            int x = i + dx[k] * arr[i][j], y = j + dy[k] * arr[i][j]; //새로운 x,y 좌표 생성
            if (x >= N || y >= N || visited[x][y]) //새로운 만든 좌표가 범위를 벗어나면 continue
                continue;

            visited[x][y] = true; //아니면 방문 여부를 true로 바꾸고 dfs 호출.
            dfs(x, y);
        }
    }
}