[JAVA]SWEA_1238_contact

문제링크

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

SW Expert Academy

 

 

 

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

public class Solution {

	static int N, V;
	static List<Integer> list[];
	static boolean isVisited[];
	static int max;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int t = 0; t < 10; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			N = Integer.parseInt(st.nextToken());
			V = Integer.parseInt(st.nextToken());

			list = new ArrayList[101];
			isVisited = new boolean[101];
			for (int i = 1; i < 101; i++)
				list[i] = new ArrayList<>();

			st = new StringTokenizer(br.readLine());
			while (st.hasMoreTokens()) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());

				list[from].add(to);
			}
			max = 0;
			bfs();
			System.out.println("#"+(t+1)+" "+max);

		}
	}

	static void bfs() {
		Queue<int[]> q = new LinkedList<>();

		q.offer(new int[] { V, 1 }); // 현재 시작 노드 넣어줌
		int cnt = 0;

		while (!q.isEmpty()) {
			int arr[] = q.poll();
			int start = arr[0];

			int size = list[start].size();
			for (int i = 0; i < size; i++) {
				int next = list[start].get(i);

				if (!isVisited[next]) {
					isVisited[next] = true;
					q.offer(new int[] { next, arr[1] + 1 });
				}
			}

			// max 값 구하기
			if (arr[1] > cnt) {// 지금부터 마지막에 도착한 애면
				max = arr[0];
				cnt = arr[1];
			}
			else if (arr[1] == cnt) {
				max = Math.max(max, arr[0]);
			}
		}
	}
}

 

 

List 사용해여 그래프 구현

 

문제 조건에서 1-100까지의 정수만 입력된다고 주어져 list와 isVisited는 모두 size 101로 초기화 시켜 주었다.

 

N = 전체 입력받는 수

V = 시작 vertex

 

list배열 초기화 후 입력을 list에 넣어준다.

여기서 가장 마지막에 도착한 부분을 구하는 것이 헷갈렸다.

처음에는 for문 안에서 내 현재 vertex에 대해 방문할 수 있는 곳이면 따로 만들어놓은 ArrayLIst에 삽입하여

큐가 끝나고 난 뒤 max값을 찾을려고 하였으나

생각해보니 연락은 동시다발적?으로 이루어지기 때문에 이렇게 구현하면 안되었다.

 

근데 얼마전에 푼 백준의 토마토 문제와 유사하여 토마토에서 적용했던 부분을 따와서 해결하였다.

https://dang2dangdang2.tistory.com/89?category=961201

[JAVA]백준_7576_토마토

토마토 부분이 궁금하시면 여기 글 보시면 됩니다.

 

 

맨 처음 큐에 삽입할 때 현재 vertex의 값만 삽입하는 것이 아니라 내가 현재 몇번째로 탐색하고 있는지를 알기위해 정수를 하나 더 추가해서 삽입해 주었다.

그래서 초반에는  q.offer(new int[]{vertex,1})  의 값이 들어가진다.

 

후에 bfs안에서 방문할 수 있는 곳이면 다시 큐에 삽입하는데

이때 q.offer(new int[]{vertex,현재몇번쨰로 탐색하고있는지 +1)}; 을 삽입해 주었다.

 

그래서 포문이 끝나고 난 뒤

이 부분을 통해서 max값을 구해주었다.

arr[1]이 현재 몇번째로 탐색하고 있는지를 저장하고 있기 때문에 그 이전보다 마지막으로 탐색한 아이면 max값을 일단 현재아이로 setting해주고 cnt도 가장마지막으로 탐색한 것으로 해준다.

 

후에 현재 탐색 수와 cnt가 같다면 그 중에서 가장 큰 것을 골라주었다.