[코드트리 챌린지] 7주차 - 시뮬레이션(격자 안에서 단일 객체를 이동)

문제링크

https://www.codetree.ai/cote/13/problems/move-to-larger-adjacent-cell?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 상하좌우에 우선순위가 존재한다. 따라서 dr, dc 만들 때 순서를 주의한다.
• 가장 큰 숫자로 가는 것이 아니라 가장 큰 숫자가 여러개이면 우선순위가 높은 방향으로 이동한다. 
  • 따라서 우선순위에 맞게 dr, dc를 설정하고 나보다 더 큰 숫자가 있으면 다음 방향은 보지 않고 움직인다.
• simulate를 돌리는 기준이 필요하다.
  
  • 현재위치(cr, cc)의 다음위치(nr, nc)가 우선 격자내에 존재하고 & 나보다 큰 숫자가 있으면 반드시 움직일 수 있으므로 simulate()할 수 있다.

 

2. 코드(Java)

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

public class Main {
    private static final int MAX_N = 100;
    public static final int DIR_NUM = 4;

    private static int n, cr, cc;
    private static int[][] board = new int[MAX_N][MAX_N];;

     // 상, 하, 좌, 우 - 우선순위 순서
    private static int[] dr = new int[]{-1, 1, 0, 0};
    private static int[] dc = new int[]{0, 0, -1, 1};

    // 격자 안에 들어가는지 확인
    private static boolean inRange(int r, int c){
        return 0 <= r && r < n && 0 <= c && c < n;
    }
    // 진행 판단
    private static boolean stop(int cr, int cc){
        for(int i = 0; i < DIR_NUM; i++){
            int nr = cr + dr[i];
            int nc = cc + dc[i];
            if(inRange(nr, nc) && board[cr][cc] < board[nr][nc]){
                return true;
            }
        }
        return false;
    }

    private static void simulate(){
        int maxNum = board[cr][cc];
        int maxcr = cr, maxcc = cc;

        for(int i = 0; i < 4; i++){
            int nr = cr + dr[i];
            int nc = cc + dc[i];

            if(inRange(nr, nc) && board[nr][nc] > maxNum){
                maxNum = board[nr][nc];
                maxcr = nr;
                maxcc = nc;
                break;
            }
        }
        cr = maxcr;
        cc = maxcc;
        // System.out.println(cr + " " + cc);
        System.out.print(board[cr][cc]+ " ");
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        cr = Integer.parseInt(st.nextToken());
        cc = Integer.parseInt(st.nextToken());

        //1base
        cr--;
        cc--;
        // board 채우기
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 시작점
        System.out.print(board[cr][cc]+ " "); 
        while(stop(cr, cc)){
            simulate();
        }
    }
}

 

※ 실력진단

PS. 자료구조를 많이 안풀어서 생각해보니까 자료구조로 했으면 엄청 쉬운 문제였네...;;; 자료구조도 좀 공부하자!