[실버 5, 1] 백준 16173, 16174번 자바(JAVA) - 점프왕 쩰리 (Small, Large)

문제 설명

문제

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

1. ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
2. ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
3. ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
4. ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
5. ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.

새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

입력

입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.

입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.

게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

출력

‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.

---

풀이

예제를 대입한 3x3 점프 게임의 그림을 그리고 그림을 보면서 풀이를 작성해보았다.

1. 칸의 숫자만큼 오른쪽 또는 아래쪽으로 움직일 수 있음
2. 해당 숫자만큼 먼저 y축을 더하여 이동
3. 해당 숫자만큼 이동했을 때
   칸을 넘어가지 않으면 다시 해당 숫자만큼 X축을 더하여 이동
4. 해당 숫자만큼 이동했을 때
   칸을 넘어가면 종료하여 다시 제자리로
5. 도착하지 않았다면 같은 방법으로
   해당 숫자만큼 Y축을 더하여 이동
6. 도착점에 도착하지 못했다면 "Hing"을 리턴
7. 도착점에 도착했다면 "HaruHaru" 리턴

위의 풀이대로 화살표를 그려 한눈에 본다면 아래와 같이 표현할 수 있다.

빨간 선 : 칸 밖으로 넘어가면서 해당 조건을 더 이상 진행하지 못하는 선

검정선 : 진행되었던 선

파랑선 : -1을 만나면서 진행되는 선

 

문제를 진행하기 위해 메서드 하나를 생성하였다.

재귀를 워낙 이해하지 못하고 사용하기 어려워했는데, 이 문제를 풀기 위해서는 재귀를 꼭 써야겠다고 생각했다.

 

아래는 재귀를 그림으로 표현한 것이다.

이미지가 많으므로 접어두겠습니다.

 

재귀를 이미지화한 코드 진행

코드

package study14;

import java.io.*;
import java.util.StringTokenizer;

public class Number_16173_점프왕쩰리2 {
    static int[][] map;
    static boolean[][] visited = new boolean[3][3];
    static int N;
    static String result = "Hing";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[j][i] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
        bw.write(search(0, 0));
        bw.flush();
        bw.close();
    }

    public static String search(int x, int y) {
        visited[x][y] = true;

        if (map[x][y] == -1) {
            return result = "HaruHaru";
        } else {
            if (x + map[x][y] < N && !visited[x + map[x][y]][y]) {
                search(x + map[x][y], y);
            }
            if (y + map[x][y] < N && !visited[x][y + map[x][y]]) {
                search(x, y + map[x][y]);
            }
        }
        return result;
    }
}

1. 좌표의 위치를 명확하게 하기 위하여 2차원 배열을 사용

2. 해당 위치를 방문했는지 확인하기 위해 boolean형 2차원 배열 사용

3. 메서드 return의 기본값을 "Hing"으로 설정.

4. 첫 제출 시 메모리가 초과되어 메모리를 아낄 수 있지 않을까 하는 생각에 BufferedReader, BufferWriter 사용 

 

특이점

메모리 초과

처음 제출 시에 boolean [][] visited를 생성하지 않고 메서드를 구현하는 바람에

메모리 초과가 발생했다.

위의 이미지를 보면 map [0,1]에서 map [1,1]로 재방문하는 경우가 발생하는데 이때 visited 변수를 만들지 않고

진행했다면 다시 방문해서 또 다음 칸으로, 다음 칸으로 재방문을 하는 일이 발생하였을 것이다.

boolean형 변수 하나를 생성함으로써 재방문을 방지하고 이로써 메모리를 아낄 수 있게 되었다.

 

[실버 1] 16174번 점프왕 쩰리 (Large)

점프왕 쩰리 (small)과 점프왕 쩰리 (Large)의 다른 점은 게임 구역의 크기이다.

Small의 경우 N(2 <= N <= 3)이지만

Large의 경우 N(2 <= N <= 64)로 구역이 확 넓어지는 것을 알 수 있다.

 

구현한 코드에서 boolean의 범위를 아래와 같이 변경하고 제출하였을 때 통과하였다.

static boolean[][] visited = new boolean[3][3];

static boolean[][] visited = new boolean[64][64];

Retrun 하는 시간을 줄일 수 있을까 생각하고

result의 값이 "HaruHaru"가 되었을 때 코드 진행을 막고 바로바로 리턴하는 if문을 다음과 같이 추가하였다.

if(result.equals("HaruHaru")){
    return result;
}

Large의 경우에는 4ms의 시간을 단축할 수 있었으나

Small의 경우에는 오히려 4ms의 시간이 더 늘어난 것을 볼 수 있었다.