[코드트리/INTERMEDIATE LOW] 상한 귤 (JAVA)

📖 문제

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

 

 

 

💡  풀이 방식

• (시작점이 여러 개인) BFS

- 처음 상해있는 귤들을 전부 시작점으로 잡아 그 위치들을 큐에 추가하고, BFS는 한 번 수행한다.

▷ 시간 복잡도 : O(N^2)

 

 

🔺 코드

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;
    static int[][] map, ans;
 
    static Queue<int[]> q = new ArrayDeque<>();
 
    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());
 
        map = new int[n][n];
        for(int i = 0 ; i < n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < n ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
 
                if(map[i][j] == 2)  q.add(new int[]{i, j});    // 상한 귤은 큐에 바로 추가한다.
            }
        }
 
        ans = new int[n][n];
       bfs(); // BFS 한 번만 하면 된다 !
        print();
    }
 
    private static void bfs() {
        while(!q.isEmpty()) {
            int[] now = q.poll();
 
            for(int dir = 0 ; dir < 4 ; dir++) {
                int nx = now[0] + dx[dir];
                int ny = now[1] + dy[dir];
 
                if(canGo(nx, ny)) {
                    q.add(new int[]{nx, ny});
                    ans[nx][ny] = ans[now[0]][now[1]] + 1;    // 상하기까지 걸리는 시간 갱신
                }
            }
        }
    }
 
    // 격자 범위 내에 있고, 상하지 않은 귤(1)이 놓여 있고, 방문한 적 없다면 방문 가능
    private static boolean canGo(int x, int y) {
        return (inRange(x, y) && map[x][y] == 1 && ans[x][y] == 0);
    }
 
    // 격자 범위 내에 있는지 판별용 함수
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < n && 0 <= y && y < n);
    }
 
    // 걸린 시간 저장한 2차원 배열 출력용 함수
    private static void print() {
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                if(map[i][j] == 0) ans[i][j] = -1;
                if(map[i][j] == 1 && ans[i][j] == 0) ans[i][j] = -2;
                sb.append(ans[i][j]).append(" ");
            }
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
}

 

---

💦 어려웠던 점

21분 소요.. 재밌었다!!

 

 

🧐 새로 알게 된 내용

BFS 할 때 여러 시작점을 두고 걸린 시간을 기록하면,

각 칸으로부터 가장 가까운 시작점으로부터 걸리는 시간을 구할 수 있다.

(BFS 특성 상 큐를 사용하므로 시작점으로부터 거리가 더 가까운 정점들을 먼저 큐에서 빼주니까 가능)

 

 

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

---

(참고)

✔ 코드트리