[Silver I] 점프왕 쩰리 (Large) - 16174 (JAVA)

문제 요약

‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.

‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.
새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

---

문제 분석

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    // 1차시도 메모리 초과.
    static int N;
    static int[][] map;
    static boolean[][] v;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        StringTokenizer st;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int idx = 0;
            while(st.hasMoreTokens()){
                map[i][idx++] = Integer.parseInt(st.nextToken());
            }
        }
        v = new boolean[N][N];
        v[0][0] = true;
        String answer = dfs(0,0) ? "HaruHaru" : "Hing";
        System.out.println(answer);
    }

    // 이동 가능한 방향은 오른쪽과 아래 뿐
    static int[] dr = {0, 1};
    static int[] dc = {1, 0};
    private static boolean dfs(int R, int C) {
        // 도착지에 도달했는지 확인
        if (map[R][C] == -1) {
            return true;
        }

        // 이동 가능한 두 방향(오른쪽, 아래)에 대해 반복
        for (int d = 0; d < 2; d++) {
            int nr = R + dr[d] * map[R][C];
            int nc = C + dc[d] * map[R][C];

            // 범위를 초과하지 않고, 해당 위치를 방문하지 않았다면?
            if (!isOutOfRange(nr, nc) && v[nr][nc] == false) {
                v[nr][nc] = true;  // 방문 처리

                // 다음 위치에서의 DFS 결과가 true라면, 현재 위치에서도 true를 반환
                if (dfs(nr, nc)) {
                    return true;
                }
            }
        }

        // 모든 방향을 확인했는데도 도착지에 도달하지 못했다면, 현재 위치에서는 도착지에 도달할 수 없음
        return false;
    }

    // 주어진 좌표가 유효한 범위 내에 있는지 확인
    private static boolean isOutOfRange(int r, int c) {
        return r < 0 || c < 0 || r >= N || c >= N;
    }

}

---

정리

새로 배운 내용

없음

개선할 점

메모리 부족과 시간초과 두 개의 문제가 있었다. 메모리 문제는 방문배열의 오사용으로 인한 문제였지만, 시간초과문제는 방문배열의 변경여부가 문제였었다.

위 문제에서 이동할 수 있는 방향은 오른쪽과 아래라고 지정해 줬고, 그 두 방향으로 이동하면 현재 위치로 다시 돌아올 일은 없다. 그러므로 방문배열을 되돌려 줄 필요가 없었다. 이렇게 하니 시간초과를 해결할 수 있었다.

더 찾아볼만한 사항

없음

---