[코드트리] 방향에 맞춰 최대로 움직이기(Java)

문제 링크

https://www.codetree.ai/trails/complete/curated-cards/challenge-max-movements-with-direction/description

Code Tree | Learning to Code with Confidence

 

내 풀이

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

public class Main {

    static class Point {
        int value;
        int dir;

        Point(int v, int d) {
            value = v;
            dir = d;
        }
    }

    static int n;
    static Point[][] grid;
    static int[] dxs = new int[] {0, -1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dys = new int[] {0, 0, 1, 1, 1, 0, -1, -1, -1};
    static int r;
    static int c;
    static int max = Integer.MIN_VALUE;

    static void recur(int x, int y, int count) {
        Point cur = grid[x][y];
        int curValue = cur.value;
        int curDir = cur.dir;
        
        int nx = x; int ny = y;
        while (true) {
            nx += dxs[curDir];
            ny += dys[curDir];

            // 다음 갈 좌표가 범위 밖 -> 진행 못함 끝
            if (!inRange(nx, ny)) {
                max = Math.max(max, count);
                return;
            }

            // 범위 안이긴 한데, 현재 값보다 작은 경우 -> 다음 좌표로 진행
            if (grid[nx][ny].value < curValue) continue;

            recur(nx, ny, count + 1);
        }
    }

    static boolean inRange(int nx, int ny) {
        return 0 <= nx && nx < n && 0 <= ny && ny < n;
    }

    public static void main(String[] args) throws IOException {
        // Please write your code here.
        // 각 칸마다 중복 없는 1 ~ n*n 숫자 & 여덟 방향 중 하나
        // 다음 방향 숫자가 더 커야 이동 가능(방향에 있는 모든 숫자들로 이동 가능)

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        grid = new Point[n][n];
        StringTokenizer st; 
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                grid[i][j] = new Point(Integer.parseInt(st.nextToken()), 0);
            }
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                grid[i][j].dir = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken()) - 1;
        c = Integer.parseInt(st.nextToken()) - 1;

        recur(r, c, 0);
        System.out.println(max);
    }
}

설명

Point 클래스

• 각 좌표에 대해서 값(value)과 방향(dir)을 저장하고 있는 클래스!

recur()

• while문을 통해 현재 좌표에서 주어진 방향으로 다 가보기
• 다음 좌표가 n x n 범위 밖이라면 더 이상 진행 불가능
  • 끝이라고 판단해 현재 이동한 횟수 count 를 전역 변수 max와 비교함
  • max에는 최대 이동 횟수가 저장되도록 함
• n x n 범위 안에 있긴 하지만 현재 값보다 작은 경우
  • 다음 좌표로 넘어가기 위해 continue
• n x n 범위 안에 있고 && 현재 좌표 값보다 큰 경우
  • 이동 횟수 + 1 하면서 재귀적으로 함수 호출!