[BOJ] 16174 - 점프왕 쩰리 (Large)

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/16174

16174번: 점프왕 쩰리 (Large)

난이도: 골드 5

사용언어: JAVA

 

풀이

이 문제는 BFS를 사용하여 간단하게 해결할 수 있는 문제입니다. BFS를 사용하여 각각의 칸 마다 해당 숫자 만큼 점프를 해주되, 테이블을 벗어나는 범위만 체크해주면 쉽게 해결 할 수 있습니다.

 

저는 처음에 이동 방향이 오른쪽과 아래쪽 밖에 없기 때문에 굳이 방문 체크를 하지 않고 풀었었지만, 이렇게 풀면 메모리 초과가 나는 것을 확인할 수 있습니다. 따라서 아무리 이동 방향이 단순해도 방문체크는 꼭 해주어야 합니다.

 

import java.io.*;
import java.util.*;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int[][] arr;
    static boolean[][] visit;
    static int[][] d = {{0, 1}, {1, 0}};
 
    static class position {
        int x;
        int y;
 
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    static Queue<position> q = new LinkedList<>();
 
    static void bfs(position p) throws IOException {
        int nx, ny;
        for (int i = 0; i < 2; i++) {
            nx = p.x + (d[i][0] * arr[p.x][p.y]);
            ny = p.y + (d[i][1] * arr[p.x][p.y]);
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && visit[nx][ny] != true) {
                if (arr[nx][ny] == -1) {
                    bw.write("HaruHaru\n");
                    bw.flush();
                    bw.close();
                    br.close();
                    System.exit(0);
                }
                visit[nx][ny] = true;
                q.add(new position(nx, ny));
            }
        }
 
    }
 
    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        visit = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        q.add(new position(0, 0));
        visit[0][0] = true;
        while (!q.isEmpty()) {
            int k = q.size();
            for (int i = 0; i < k; i++) {
                bfs(q.poll());
            }
        }
 
        bw.write("Hing\n");
        bw.flush();
        bw.close();
        br.close();
    }
}