[코드트리/NOVICE MID] 숫자가 더 큰 인접한 곳으로 이동 (JAVA)

📖 문제

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

 

 

 

💡  풀이 방식

• 시뮬레이션

입력받은 시작점 (r,c)에서부터 우선순위가 상하좌우일 때 현재 칸보다 큰 값을 가진 칸으로 바로 이동할 수 있는지 확인한다. (boolean으로 확인)

그 칸에서 이동할 수 있다면, 해당 칸을 경로 리스트에 넣어 출력한다.

 

상하좌우로 이동할 수 없다면, 종료한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};   // 우선순위 : 상하좌우
    static int[] dy = {0, 0, -1, 1};
 
    static int n, curX, curY;
    static int[][] map;
    static StringBuilder sb = new StringBuilder();
 
    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());
        curX = Integer.parseInt(st.nextToken());
        curY = Integer.parseInt(st.nextToken());
 
        map = new int[n + 1][n + 1];
        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < n ; j++) {
                map[i][j + 1] = Integer.parseInt(st.nextToken());
            }
        }
 
        sb.append(map[curX][curY] + " ");
 
        while(true) {
            boolean exists = simulate();    // 상하좌우 이동할 수 있는지 확인
 
            if(!exists) // 상하좌우로 이동할 수 없다면 종료
                break;
            
            sb.append(map[curX][curY] + " ");
        }
 
        System.out.println(sb);
    }
 
    private static boolean simulate() {
        for (int d = 0; d < 4; d++) {
            int nx = curX + dx[d];
            int ny = curY + dy[d];
 
            // 격자 범위 내에 있고, 현재 칸의 값보다 더 값이 크다면 그 칸으로 바로 이동하도록 true 반환
            if (inRange(nx, ny) && map[nx][ny] > map[curX][curY]) {
                curX = nx;
                curY = ny;
                return true;
            }
        }
 
        return false;   // 4방향 다 이동할 수 없다면, 움직임 종료하게 false
    }
 
    private static boolean inRange(int x, int y) {
        return (1 <= x && x <= n && 1 <= y && y <= n);
    }
}
 

 

 

---

💦 어려웠던 점

- 더 이상 이동할 곳이 없을 때까지 움직임 → while문을 활용할 생각을 못 했다.

- BFS처럼 이동 가능한 칸으로 큐에 추가해서 바로 이동하고 방문하게 하려고 했는데 틀렸다 ㅎㅎ

- 조건을 만족하는 칸을 찾으면 해당 칸의 값 저장하고, 바로 메소드 종료하게 해서 해당 칸에 대해 적용되게 하기,, (바로 return true)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리