[백준] 18352번 특정 거리의 도시 찾기 JAVA (자바) 풀이

문제 18352번 (bfs)

 :  1번 ~ N번까지의 도시와 M개의 단방향 도로가 존재 (모든 도로의 거리는 1)

 

 :  도시 X로부터 출발해 도달할 수 있는 도시 중에서, 최단 거리 K인 도시 모두 출력

    자신에서 다시 자신으로 가는 최단 거리는 항상 0

 

 

예) N=4, K=2, X=1

 

최단 거리가 2인 도시는 4번 도시 뿐이다

3은 2를 거쳐서 가면 거리가 2가 되지만 답은 최단거리를 구하는 것으로
3의 최단거리는 1-3이라 즉 1이 되기 때문에 답이 될 수 없다

 

 

 [입력]

 :  첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X

    (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N)

 :  둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B ( A번 도시에서 B번 도시로 이동하는 도로)

    (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수

 

 

[출력]

 :  X에서 도착지까지 최단 거리가 K인 도시의 번호를 한 줄에 하나씩 오름차순 출력

    (최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력)

 

[설명]

 

1. int count 가 아닌 int count[] 배열 이용하기

• 그냥 count 사용 시 코드가 너무 지저분해져서 배열 사용
• count[next] = count[p] + 1 사용
• 인덱스로 노드 이동 / 거리를 배열 안에 담기
• 처음엔 -1로 모두 통일하고 bfs 들어가는 애들은 0으로 초기화 후 카운트 한

 

2. count[i] = -1 은 visit[i] = false와 같다

• count를 -1 로 초기화한 것은 방문하지 않았다는 뜻
• count를 0으로 초기화한 것은 시작 노드만 해당 (방문처리)
• count[p] + 1 을 통해 0 이상으로 카운트 갱신 (방문의 의미)
• 고로 visit 함수가 필요없지만 직관적인 이해를 돕기위해 썼다

3. 출력 시 boolean found 사용

• bfs의 최종 결과인 count가 K가 아닌 경우를 !found라고 설정
• 최종 결과가 K라면 found = true로 설정
• !found 일 경우 -1 출력

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,M,K,X,start,end,count[];
    static ArrayList<Integer> arr[];
    static boolean visit[];
    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());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        arr = new ArrayList[N+1];
        count = new int[N+1];
        visit = new boolean[N+1];
        
        for(int i=1; i<=N; i++){
            arr[i] = new ArrayList<>();
            count[i]= -1;
        }
        
        while(M-->0){
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());
            arr[start].add(end);
        }
        
        bfs();
        
        boolean found = false;
        for(int i=1;i<=N;i++){
            if(count[i]==K){
                System.out.println(i);
                found = true;
            }
        }
        if(!found){
            System.out.println("-1");
        }
    }
    
    static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.add(X);
        visit[X]=true;
        
        count[X]=0;
        
        while(!q.isEmpty()){
            int p = q.poll();
            for(int i=0; i<arr[p].size(); i++){
                for(int next: arr[p]){
                    if(!visit[next]){
                        q.add(next);
                        visit[next]=true;
                        count[next]=count[p]+1;
                    }
                }
            }
        }
    }
}

 

 [해설]
     

 :  static int N,M,K,X,start,end,count[];  
    static ArrayList<Integer> arr[];
    static boolean visit[];
    

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());  노드 개수
    M = Integer.parseInt(st.nextToken());  노드 간선 수
    K = Integer.parseInt(st.nextToken());  목표 노드 위치
    X = Integer.parseInt(st.nextToken());  현재 노드 위
        

 :  arr = new ArrayList[N+1];  노드 연결 표시
    count = new int[N+1];  결과 출력할 count 배열
    visit = new boolean[N+1];  방문 배열
        
 :  for(int i=1; i<=N; i++){  N이 1부터 시작한다 
            arr[i] = new ArrayList<>();  인덱스 순서대로 N개 채워 넣기
            count[i]= -1;  -1 로 초기화 (boolean false나 마찬가지)
    }
        
 :  while(M-->0){
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());  연결노드1
            end = Integer.parseInt(st.nextToken());  연결노드2
            arr[start].add(end);  연결노드들 관계 표현
        }
        
 ;  bfs();  bfs 시작
        
 :  boolean found = false;  초기화

    for(int i=1;i<=N;i++){  count배열 순서대로 돌면서 K거리인 인덱스 찾기
            if(count[i]==K){  
                System.out.println(i);  해당 인덱스 즉 노드 출력
                found = true;  
            }
    }
    if(!found){  found가 true가 아닐 경우 거리가 K인 경우가 한 순간도 없다는 것
            System.out.println("-1");  -1 출력
    }
  
    
 :  static void bfs(){  
        Queue<Integer> q = new LinkedList<>();  큐선언
        q.add(X);  큐에 시작 위치 추가
        visit[X]=true;  방문처리 (사실상 count가 -1 or 아니냐로 구분하기 때문에 필요없음)
        
        count[X]=0;  시작 위치 -1이 아닌 0으로 갱신 (방문처리)
        
        while(!q.isEmpty()){
            int p = q.poll();  큐에서 꺼내고
            for(int i=0; i<arr[p].size(); i++){  
                for(int next: arr[p]){  꺼낸 p와 연결된 다른 노드들 둘러보기
                    if(!visit[next]){  해당 노드를 방문하지 않았다면
                        q.add(next);  다음 연결노드로 큐에 추가
                        visit[next]=true;  방문처리
                        count[next]=count[p]+1;  방문처리이자 거리 계산
                    }
                }
            }
        }
    }



   

 

      

이제 풀어보러 갈께요 :)

 

 

 

https://www.acmicpc.net/problem/18352

 

 

 

 

 

 

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