Baekjoon/[5] DFS & BFS

[백준] 2589번 보물 JAVA (자바) 풀이

Poorm 푸름 2024. 6. 21. 04:24

문제 2589(BFS)

 

 :  보물섬 지도의 각 칸은 육지(L)나 바다(W)로 표시

    이동은 상하좌우로 이웃한 육지로만 가능, 한 칸 이동하는데 한 시간이 걸린다

    보물은 육지 두 곳에 나뉘어 묻혀있고 두 곳을 이동하는 최단거리를 구해라

    같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다

 

 예) 보물은 아래 표시된 두 곳에 묻혀 있고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간

 

 

[입력]


 :  첫째 줄에는 지도의 가로, 로 ( 가로, 세로의 크기는 각각 50이하 )

 :  다음 줄부터 L과 W로 표시된 보물 지도 (빈칸없이)

 

 

 [출력]


 :  보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력

 

 

 

 [문제접근]

 

1. 출력 배열 사용하지 말고 큐에다 넣어버리기

  • count[] 배열보다 큐 자체에 넣는 것이 더 간단하다 q.add(new int{x,y,0}) 추천

 

2. 최단거리를 구해라 단 2개의 보물 위치는 가장 긴 것으로!

  • 최단거리는 bfs가 해결해준다

  • 2개의 보물 위치 거리가 가장 길어야 하므로 Math.max를 사용
    • 시작지점 기준으로 구별
      main메서드에서 시작 노드 별 카운트한 값 중 가장 높은 것을 answer에 저장

    • 도착지점 기준으로 구별
      bfs에서 하나의 시작 노드를 정해놓고 갈 수 있는 모든 땅을 가보고 카운트한 것 중 가장 높은 값을 result에 저장

 

3. bfs를 for문이나 재귀에 사용하지 말 것

  • for(){ bfs } 하지말 것 (bfs 메서드 내에서 큐에 계속 추가하면서 반복하면 된다)
  • bfs메서드 내에서 다시 bfs를 호출하지 말 것 (백트래킹이나 dfs와는 다르다)

       

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int M,N;
    static char arr[][];
    static boolean visit[][];
    static int dx[]={-1,1,0,0};
    static int dy[]={0,0,-1,1};
    
    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());
        arr = new char[N][M];
        int answer = 0;
        
        for(int i=0; i<N; i++){
            arr[i] = br.readLine().toCharArray();
        }
        
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(arr[i][j]=='L'){
                    visit = new boolean[N][M];
                    answer = Math.max(answer,bfs(i,j));
                }
            }
        }
        
        System.out.println(answer);
    }
    
    static int bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y,0});
        visit[x][y]=true;
        int result =0;
        
        while(!q.isEmpty()){
            int p[] = q.poll();
            for(int i=0; i<4;i++){
                int nx = p[0]+dx[i];
                int ny = p[1]+dy[i];
                if(0<=nx&&nx<N && 0<=ny&&ny<M && arr[nx][ny]=='L' && !visit[nx][ny]){
                    q.add(new int[]{nx,ny,p[2]+1});
                    visit[nx][ny]=true;
                    result = Math.max(result,p[2]+1);
                }
            }
        }
        
        return result;
    }
}

 

 [해설]
     

 :  static int M,N;
    static char arr[][];  입력 문자열
    static boolean visit[][];  방문기록
    static int dx[]={-1,1,0,0};  이동할 x좌표
    static int dy[]={0,0,-1,1};  이동할 y좌표
    
 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());  행개수 (세로)
    M = Integer.parseInt(st.nextToken());  열개수 (가로)
    arr = new char[N][M];  입력 배열
    int answer = 0;  
        
 :  for(int i=0; i<N; i++){
            arr[i] = br.readLine().toCharArray();  문자열 입력받기
    }
        
 :  for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(arr[i][j]=='L'){  L일 경우에만 bfs의 시작노드가 될 수 있음
                    visit = new boolean[N][M];  bfs 전에 방문배열 초기화
                    answer = Math.max(answer,bfs(i,j));  bfs 결과 중 최대값 뽑기
                }
            }
    }
        
 :  System.out.println(answer);  최장거리가 보물의 위치가 되므로 출력 
    
    
 :  static int bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();  큐선언
        q.add(new int[]{x,y,0});  큐에 추가
        visit[x][y]=true;  방문 처리
        int result =0;  
        
        while(!q.isEmpty()){
            int p[] = q.poll();  큐에서 뽑기
            for(int i=0; i<4;i++){  4방향으로 이동가능
                int nx = p[0]+dx[i];  새로운 다음 x좌표
                int ny = p[1]+dy[i];  새로운 다음 y좌표
                if(0<=nx&&nx<N && 0<=ny&&ny<M && arr[nx][ny]=='L' && !visit[nx][ny]){  이동 가능하다면
                    q.add(new int[]{nx,ny,p[2]+1});  큐에 추가하고 마지막에 횟수 카운트
                    visit[nx][ny]=true;  방문처리
                    result = Math.max(result,p[2]+1);  도착지점이 어디인 지 모르니까 max값으로 구분하기
                }
            }
        }
        
        return result;  최종 result 출력
   }




 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

 

 

 
저작자표시