[코드트리/INTERMEDIATE LOW] K번 최댓값으로 이동하기 (JAVA)

📖 문제

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

 

 

 

💡  풀이 방식

• BFS

1) 현재 위치에서 이동 가능한 칸 전부 찾기
2) 도달 가능한 칸 中 우선순위가 가장 높은 칸 위치 구하기
  - 도달 가능한 칸 있다면, 현재 칸 위치를 해당 위치로 옮기기
  - 도달 가능한 칸 없다면, 움직이기 종료

 

시작 위치에서 상하좌우에 본인보다 작은 값이 없다면, 이동할 수 없으므로 종료한다.

하지만 본인보다 작은 값이 존재한다면, 아래와 같이 진행한다.

 

1) bfs를 통해 배열을 탐색하며 방문 가능한(=격자 범위 내에 있고, 방문한 적 없고, 기준 점의 값보다 작은) 모든 점들을 방문하고, 이 점들을 리스트에 추가한다.

 

2) 점들을 저장한 리스트는 "숫자>행>열" 순으로 정렬해 우선순위가 가장 높은 칸의 위치를 구하고 이동한다. (=정렬 후 리스트의 0번째 값)

조건
1. 도달할 수 있는 칸들에 적힌 숫자들 중 최댓값으로 이동한다.
2. 1번 조건을 만족하는 숫자가 여러개인 경우, 행 번호가 가장 작은 곳으로 이동한다.
3. 2번 조건을 만족하고, 행 번호도 같은 숫자가 여러개인 경우, 열 번호가 가장 작은 곳으로 이동한다.

class Node implements Comparable<Node> {
    int r, c, val;

    public Node(int r, int c, int val) {
        this.r = r;
        this.c = c;
        this.val = val;
    }

    @Override
    public int compareTo(Node n) {
        if(this.val == n.val) { // [칸의 값이 같은 경우]
            if(this.r == n.r) { // 행 번호가 같다면, 열 기준 오름차순 정렬
                return this.c - n.c;
            }
            return this.r - n.r;    // 행 번호가 다르다면, 행 기준 오름차순 정렬
        }
        return n.val - this.val;    // [칸의 값이 다른 경우] 값 기준 내림차순 정렬
    }
}

 

 

 

🔺 코드

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, K, r, c;
    static int[][] grid;
    static boolean[][] visited;
 
    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());
        K = Integer.parseInt(st.nextToken());
 
        grid = 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++) {
                grid[i][j + 1] = Integer.parseInt(st.nextToken());
            }
        }
 
        st = new StringTokenizer(br.readLine(), " ");
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
 
        while(K-->0){
            if(!smallerNumberExists())  // 상하좌우에 작은 값이 없어 이동할 수 없다면 pass
                break;
 
            // 상하좌우로 이동할 수 있다면, bfs 수행
            visited = new boolean[N + 1][N + 1];    // 방문배열 매번 초기화해야 함
            bfs();
        }
 
        System.out.println(r + " " + c);
    }
    
    // 상하좌우에 현재 칸의 값보다 작은 값이 존재하는지 확인하는 함수
    private static boolean smallerNumberExists() {
        for(int d = 0 ; d < 4 ; d++) {
            int nr = r + dx[d];
            int nc = c + dy[d];
 
            if(inRange(nr, nc) && grid[nr][nc] < grid[r][c])
                return true;
        }
 
        return false;
    }
 
    // 격자를 벗어나는지 확인하는 함수
    private static boolean inRange(int r, int c) {
        return (1 <= r && r <= N && 1 <= c && c <= N);
    }
 
    private static void bfs() {
        List<Node> list = new ArrayList<>();    // 해당 점에서 접근 가능한 모든 칸의 정보를 저장하는 리스트
 
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(r, c, grid[r][c]));
 
        int targetNum = grid[r][c];
 
        while(!q.isEmpty()) {
            Node now = q.poll();
 
            for(int d = 0 ; d < 4 ; d++) {
                int nr = now.r + dx[d];
                int nc = now.c + dy[d];
 
                // 격자 범위 내에 있고, 방문한 적 없고, 해당 칸의 값보다 작다면, 큐와 리스트에 값 추가
                if(inRange(nr, nc) && !visited[nr][nc] && grid[nr][nc] < targetNum) {
                    visited[nr][nc] = true;
                    q.add(new Node(nr, nc, grid[nr][nc]));
                    list.add(new Node(nr, nc, grid[nr][nc]));
                }
            }
        }
 
        Collections.sort(list); // 조건에 맞게 정렬하고, 0번째 값으로 이동하도록 함
        r = list.get(0).r;
        c = list.get(0).c;
    }
}
 
class Node implements Comparable<Node> {
    int r, c, val;
 
    public Node(int r, int c, int val) {
        this.r = r;
        this.c = c;
        this.val = val;
    }
 
    @Override
    public int compareTo(Node n) {
        if(this.val == n.val) { // [칸의 값이 같은 경우]
            if(this.r == n.r) { // 행 번호가 같다면, 열 기준 오름차순 정렬
                return this.c - n.c;
            }
            return this.r - n.r;    // 행 번호가 다르다면, 행 기준 오름차순 정렬
        }
        return n.val - this.val;    // [칸의 값이 다른 경우] 값 기준 내림차순 정렬
    }
}

 

 

➕ 다른 풀이 방식

비교할 때 튜플형 비교를 할 수 있다고 한다.

첫 번째 원소를 비교하고, 두 원소가 같다면 두 번째 원소를 비교하는 식으로 진행

if (숫자1, -행1, -열1) > (숫자2, -행2, -열2):
    숫자1의 우선순위가 더 높다.
else:
    숫자 2가 우선순위가 더 높다.

 

---

💦 어려웠던 점

- 소요시간 35분! 생각보다 짧게 걸려서 기쁜,,

 

 

 

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