[SWEA][JAVA] 1238 - Contact

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD&categoryId=AV15B1cKAKwCFAYD&categoryType=CODE&problemTitle=1238&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

 

문제

 

설명

예시 그림도 있어서 문제의 길이는 꽤 긴편이었지만, 그에 비해서 난이도는 그렇게 높지 않은 문제입니다.

그래프에서 한 사이클마다 하나의 정점에서 인접한 정점으로 동시에 퍼져나가는 형태이기 때문에, BFS 유형입니다.

단방향 그래프를 표현하기 위해서 인접행렬을 사용했고, visited배열에 방문 여부와 몇 번째로 방문한 것인지를 동시에 기록하기 위해 boolean이 아닌 int로 만들었습니다.

그렇게 하면 마지막으로 방문한 노드들은 visited배열에서 마지막 순서 숫자가 적히게 되므로 bfs를 다 돌린 다음에, visited 배열을 순회하면서 그 숫자가 적힌 값들 중에 최댓값을 구하면 되는 구조입니다. 

 

 

코드

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

public class SWEA1238_Contact {
	
	static int[][] map;
	static int N, S, answer;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		for(int tc=1; tc<=10; tc++) {
			N = sc.nextInt(); //데이터의 갯수
			S = sc.nextInt(); //시작점 정점 번호
			map = new int[101][101]; //1부터 시작
			
			for(int i=0; i<N/2; i++) {
				int from = sc.nextInt();
				int to = sc.nextInt();
				map[from][to] = 1;
			}
			answer=0;
			bfs();
			System.out.println("#" + tc + " " + answer);
		}
	}

	private static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		int visited[] = new int[101]; //방문 여부 및 방문 "순서"를 기록하기 위해 int배열 선언!
		
		q.offer(S);
		visited[S]=1;
		int cur=0;
		while(!q.isEmpty()) {
			cur = q.poll();
			
			for(int i=0; i<101; i++) {
				if(visited[i]==0 && map[cur][i]==1) { //방문 전이고 서로 인접해 있다면
					q.offer(i);
					visited[i] = visited[cur]+1; //cur 바로 다음에 방문하는 것이므로
				}
			}
		}
		//cur은 마지막으로 방문했던 정점의 숫자를 가지고 있음.
		int last = visited[cur]; //마지막 순서의 값
		
		for(int i=0; i<101; i++) {
			if(visited[i]==last) {
				answer = Math.max(answer, i);
			}
		}
	}
}