[Baekjoon] 14217_그래프 탐색

Gold V

문제(출처: https://www.acmicpc.net/problem/14217)

---

< 그래프 탐색 >

 

문제 풀이

 

1. 각 도시 -> 수도로 탐색하는 방법

: 시간초과는 발생하지 않았지만 시간이 오래 걸리는 것을 확인할 수 있었다.

 

2. 수도 -> 각 도시 탐색하는 방법

: bfs를 한 번만 호출하여 답을 얻을 수 있어 1번보다 시간이 적게 걸리는 것을 확인할 수 있었다.

 

위와 같은 방법 말고는 단순 bfs를 활용하면 문제를 해결할 수 있었다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static ArrayList<ArrayList<Integer>> arr;
	static boolean visited[];
	static int result[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		
		// init
		arr=new ArrayList<>();
		for(int i=0; i<n; i++) {
			arr.add(new ArrayList<>());
		}
		
		for(int i=0; i<m; i++) { // 양방향
			st=new StringTokenizer(bf.readLine());
			int a=Integer.parseInt(st.nextToken())-1;
			int b=Integer.parseInt(st.nextToken())-1;
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		
		int q=Integer.parseInt(bf.readLine());
		for(int k=0; k<q; k++) {
			st=new StringTokenizer(bf.readLine());
			int a=Integer.parseInt(st.nextToken());
			int i=Integer.parseInt(st.nextToken())-1;
			int j=Integer.parseInt(st.nextToken())-1;
			
			if(a==1) { // 도로 생성
				arr.get(i).add(j);
				arr.get(j).add(i);
			}else { // 도로 제거
				arr.get(i).remove(Integer.valueOf(j));
				arr.get(j).remove(Integer.valueOf(i));
			}
			
			visited=new boolean[n];
			result=new int[n];
			bfs(0,0);
			for(int l=0; l<n; l++) {
				if(!visited[l]) bw.write("-1 ");
				else bw.write(result[l]+" ");
			}
			bw.write("\n");
		}
		bw.flush();
	}

	private static void bfs(int start, int depth) {
		Queue<int[]> queue=new LinkedList<>();
		queue.add(new int[] {start, depth});
		visited[start]=true;
		
		while(!queue.isEmpty()) {
			int num[]=queue.poll();
			for(int i=0; i<arr.get(num[0]).size(); i++) {
				int temp=arr.get(num[0]).get(i);
				if(!visited[temp]) {
					visited[temp]=true;
					result[temp]=num[1]+1;
					queue.add(new int[] {temp, num[1]+1});
				}
			}
		}
	}
}

 

Main

-  n(도시의 개수), m(도로의 개수) 입력

- arr : 도시 정보 저장

- q(도로 정비 계획에 들어있는 도로의 수 ) 입력 및 a, i, j 입력

- visited : 방문 여부

- result: 최소 방문 도시 저장

-  bfs를 활용하여 수도에서 다른 도시 방문 한 값을 출력

 

bfs

- queue에 {도시 번호, 방문 수} 저장

- queue가 빌 때까지 반복하며 인접 리스트를 활용하여 연결된 도시를 확인 -> 아직 방문하지 않은 곳이라면 이동하여 방문 후 result에  ( 방문 수 + 1 ) 값을 저장 및 queue에 저장해 준다.

 

---

생각🤔

 

문제 풀이에서 말한 두 가지 방법으로 문제를 해결해 봤다. 시간 차이가 나는 것을 확인할 수 있었다.

---