[백준/JAVA] 23352번: 방탈출

📖 문제

23352번: 방탈출

 

 

💡  풀이 방식

• BFS

상하좌우로 이동하며 가장 긴 경로 길이인 시작점과 끝점의 합을 구한다.

 

4방향 탐색 후, 현재 이동 거리가 최대 이동거리보다 길다면 최대 이동거리 len을 변경하고, 

시작 방과 끝 방에 적힌 숫자의 합을 구해 최댓값 max와 비교해 갱신한다.

if(!flag && now[2] >= len) { // 현재 이동 거리가 최대 이동거리보다 많으면 최대 이동거리 변경
    if(now[2] > len)
        max = start + grid[now[0]][now[1]];
    else 
        max = Math.max(max, start + grid[now[0]][now[1]]);

    len = now[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,M;
    static int[][] grid;
    
    static int len = 0; // 최대 이동 거리
    static int max = 0;
    
    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());
        M = Integer.parseInt(st.nextToken());
        
        grid = new int[N][M];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < M ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(grid[i][j] != 0)
                    bfs(i, j);
            }
        }
        
        System.out.println(max);
    }
    
    private static void bfs(int x, int y) {
        boolean[][] visited = new boolean[N][M];
        visited[x][y] = true;
        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y, 0});
        
        int start = grid[x][y];
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            boolean flag = false;
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(!inRange(nx, ny) || grid[nx][ny] == 0 || visited[nx][ny])    continue;
                
                flag = true;
                visited[nx][ny] = true;
                q.add(new int[] {nx, ny, now[2] + 1});  
            }
            
            if(!flag && now[2] >= len) { // 현재 이동 거리가 최대 이동거리보다 많으면 최대 이동거리 변경
                if(now[2] > len)
                    max = start + grid[now[0]][now[1]];
                else 
                    max = Math.max(max, start + grid[now[0]][now[1]]);
                    
                len = now[2];   // 최대 이동 거리 변경
            }
        }
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < M);
    }
}
 

 

 

---

💦 어려웠던 점

- 가장 긴 경로 구하는 방법을 틀렸다. 무조건 (0,0) & (N-1, M-1) 또는 (0, M-1) & (N-1, 0)이 최장 거리일 것이라 생각했느데 그게 아니었고 직접 거리를 구해야 했다.

- 현재 이동 거리 now[2] 가 최대 이동 거리 len 보다 같거나 클 때를 처리하는 조건문의 위치! while문 안에 넣어주자..

 

 

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

---

(참고)

[백준] 23352: 방탈출 - JAVA

 

[백준 23352번] 방탈출 - java