SWEA_1238_[S/W 문제해결 기본 10일차]-Contact

1.

구분: BFS, 그래프 이론

언어: Java

전략: 

• BFS의 기본을 잘 생각한다. 
• 정점을 방문한다면 큐에 넣고, 방문 처리를 한다. 

 

---

2. 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
	//인접 리스트로 그래프를 표현하기 위해서 클래스 생성
	static class Node{
		//그래프의 정점과 그 다음 노드 알 수 있는 링크
		int vertex; 
		Node link;
		public Node(int vertex, Node link) {
			this.vertex = vertex;
			this.link = link;
		}
	}
	
	//class를 만든다. 큐에 정점과 깊이를 넣을 것이다. 
	static class Contact{
		//현재 정점과 그 층을 나타내는 것
		int current;
		int level;
		public Contact(int current, int level){
			this.current = current;
			this.level = level;
		}
	}
	
static Node[] graph;
static boolean[] check;
public static void main(String[] args) {
	
	Scanner scanner = new Scanner(System.in);
		for(int tc =1; tc<=10; tc++) {
			
			//전체 개수 & 시작 점 수 
			int n = scanner.nextInt();
			int k = scanner.nextInt();
			graph = new Node[n];

			//from, to 이기 떄문에 n/2번만큼 반복을 돔
			for(int i = 0; i<n/2; i++) {
				int from = scanner.nextInt();
				int to = scanner.nextInt();
				//Node배열 from인덱스에 to와, 앞에서부터 넣으니까 그 담 연결도 graph[from]
				graph[from] = new Node(to, graph[from]);				
			}
			//방문 여부를 확인 하기 위한 boolean 배열
			check = new boolean[101];
		
			//초기화가 필요하다 
			max = -1;
			mlevel = -1;
			
			bfs(k,0);			
			
			System.out.println("#"+tc+" "+max);

			
		}//test
	
	}//main


//max는 최대값, mlevel은 최대 깊이 
static int max ,mlevel;

private static void  bfs(int current, int level) {
		//bfs를 위한 큐 생성
		Queue<Contact> q = new LinkedList<Contact>();
		//큐에 삽입 후 방문 처리
		q.offer(new Contact(current, level));
		check[current] = true;
		
		while(!q.isEmpty()) {
			//큐에서 하나 꺼낸다 
			Contact v = q.poll();
			
			int nc = v.current;
			int nl = v.level;
			
			//층이 변동 - 한 층 증가 --> 최대 층 변경, max값도 변경
			if(mlevel<nl) {
				mlevel = nl;
				max = nc;
			}
			//층이 같다면 - max값을 찾아라 
			else if(mlevel == nl) {
				max= Math.max(max, nc);
			}
			//current 정점과 인접한 정점들을 찾아서 방문 안하것들 큐에 넣는다. 단! 층 하나 증가
			for(Node temp = graph[nc]; temp!=null; temp = temp.link) {
				if(!check[temp.vertex]) {
					q.offer(new Contact(temp.vertex, v.level+1));
					check[temp.vertex] = true;
				}
			}			
		}
		
	}//bfs

}//class

---

3. 

• 백준의 토마토 문제와 매우 유사하다.(https://www.acmicpc.net/problem/7576)
• level이 증가함에 따라 max값을 구하는 과정이 단순해 질 수 있다.