백준 - 점프왕 쩰리 (못풀었다가 검토하다 다시 품)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/16173

 

[접근 방법]

DFS식으로 모든 방법을 조회하는 식으로 풀었는데 못풀었다.....

메모리 초과가 난다.. 모르겠다 답이 없다 이 문제는.. 애초에 BFS DFS에 약해서 제일 쉬운 문제로 골라서 푼 건데.

못풀었다. 다른 사람들 보니까 DFS로 푼 사람이 꽤 있는데도 왜 답이 안나오는지 모르겠다.

어디서 잘못된걸까

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

class Main {
    static int N;
    static int[][] map;
    // 현재 위치
    static int[] currentPosition = {0,0};      //행,열
    static int[] rightDirection = {0,1};
    static int[] downDirection = {1,0};
    static boolean[][] visited;

    public static void main(String[] args) throws Exception {
        // 입력 ㅂ다기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        // 보드판
        map = new int[N][N];
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(inputs[j]);
            }
        }

        move(rightDirection);
        move(downDirection);
        System.out.println("Hing");
    }

    private static void move(int[] moveDirection) {
        if (visited[currentPosition[0]][currentPosition[1]]) return;
        // 현재 좌표에 값 구하기.
        int valueOfCurrentCoordinate =map[currentPosition[0]][currentPosition[1]];
        // 보드 밖이면 return false
        if (currentPosition[0]+valueOfCurrentCoordinate*moveDirection[0] < 0 || N-1 < currentPosition[0]+valueOfCurrentCoordinate*moveDirection[0] || currentPosition[1] + valueOfCurrentCoordinate*moveDirection[1] < 0 || N-1 < currentPosition[1] + valueOfCurrentCoordinate*moveDirection[1]) {
            return;
        } else if (visited[currentPosition[0]+valueOfCurrentCoordinate*moveDirection[0]][currentPosition[1] + valueOfCurrentCoordinate*moveDirection[1]]) return;

        currentPosition[0] += valueOfCurrentCoordinate*moveDirection[0];
        currentPosition[1] += valueOfCurrentCoordinate*moveDirection[1];
        // 보드 밖이 아니고 현재 위치의 값이 -1이면 return true
        if (map[currentPosition[0]][currentPosition[1]] == -1) {
            System.out.println("HaruHaru");
            System.exit(0);
        }

        move(rightDirection);
        move(downDirection);
        visited[currentPosition[0]][currentPosition[1]] = true;
        currentPosition[0] -= valueOfCurrentCoordinate*moveDirection[0];
        currentPosition[1] -= valueOfCurrentCoordinate*moveDirection[1];
    }
}

 

 

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/16173

 

[내 답안 수정하기]

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    static int N;
    static int[][] map;
    static int[] currentPosition = {0,0};
    static int[] rightDirection = {0,1};
    static int[] downDirection = {1,0};
    static boolean[][] visited;

    public static void main(String[] args) throws Exception {
        // 입력 ㅂ다기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        // 보드판
        map = new int[N][N];
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(inputs[j]);
            }
        }

        if (move(rightDirection) || move(downDirection)) System.out.println("HaruHaru");
        else System.out.println("Hing");
    }

    private static boolean move(int[] moveDirection) {
        if (visited[currentPosition[0]][currentPosition[1]]) return false;
        if (map[currentPosition[0]][currentPosition[1]]==0) {
            visited[currentPosition[0]][currentPosition[1]] = true;
            return false;
        }
        // 현재 좌표에 값 구하기.
        int valueOfCurrentCoordinate =map[currentPosition[0]][currentPosition[1]];
        // 보드 밖이면 return false
        if (currentPosition[0]+valueOfCurrentCoordinate*moveDirection[0] < 0 || N-1 < currentPosition[0]+valueOfCurrentCoordinate*moveDirection[0] || currentPosition[1] + valueOfCurrentCoordinate*moveDirection[1] < 0 || N-1 < currentPosition[1] + valueOfCurrentCoordinate*moveDirection[1]) {
            return false;
        } else if (visited[currentPosition[0]+valueOfCurrentCoordinate*moveDirection[0]][currentPosition[1] + valueOfCurrentCoordinate*moveDirection[1]]) return false;

        currentPosition[0] += valueOfCurrentCoordinate*moveDirection[0];
        currentPosition[1] += valueOfCurrentCoordinate*moveDirection[1];
        // 보드 밖이 아니고 현재 위치의 값이 -1이면 return true
        if (map[currentPosition[0]][currentPosition[1]] == -1) {
            return true;
        }

        boolean isWork = move(rightDirection) || move(downDirection);
        visited[currentPosition[0]][currentPosition[1]] = true;
        currentPosition[0] -= valueOfCurrentCoordinate*moveDirection[0];
        currentPosition[1] -= valueOfCurrentCoordinate*moveDirection[1];
        return isWork;
    }
}

[반성]

얼마 전에 제출해서 틀렸으면 코드를 다시 처음부터 보는 습관을 가지라고 글을 썼다.

이번엔 진짜 그랬다. 근데 이번엔 또 뭐가 문제였냐? 문제의 조건을 제대로 파악 못했다.

분명히 map에는 0인 경우가 존재하고, 0이면 제자리에서 메서드가 계속 반복되어 스택 오버플로우가 날 수 밖에 없던 거다.

코드를 다시 보는 것도 중요하지만, 문제를!!! 다시보는 !!! 습관을 들이자. 정신 좀 차리자.

[그래도 잘한 점]

이 문제를 약 4시간 가깝게 봤다. 결과적으로 허무하게 조건문 하나 추가해주는 걸로 해결됐지만, 그래도 포기하지 않았다는 점에서 내 자신에게 박수를 쳐주고 싶다. 사실 2~3시간 정도 제자리에서 헤매다가 컴퓨터를 껐다가 심호흡 몇 번 하고 다시 켜서 풀었다.

진짜 완전 허무한 결말이지만, 그래도 포기하지 않고 풀어서 잘했다!! 앞으로도 이렇게 막혀도 포기하지 않으면 할 수 있다!! 아자아자!~~~