[백준] 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
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *