[SWEA] 1238. Contact (JAVA)

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

[문제]

비상연락망과 연락을 시작하는 당번에 대한 정보가 주어질 때, 가장 나중에 연락을 받게 되는 사람 중 번호가 가장 큰 사람을 구하는 함수를 작성하시오.

 

[제약 사항]
연락 인원은 최대 100명이며, 부여될 수 있는 번호는 1이상, 100이하이다.
단, 예시에서 5번이 존재하지 않듯이 중간 중간에 비어있는 번호가 있을 수 있다.
한 명의 사람이 다수의 사람에게 연락이 가능한 경우 항상 다자 간 통화를 통해 동시에 전달한다.
연락이 퍼지는 속도는 항상 일정하다 (전화를 받은 사람이 다음사람에게 전화를 거는 속도는 동일).
비상연락망 정보는 사전에 공유되며 한 번 연락을 받은 사람에게 다시 연락을 하는 일은 없다.
예시에서의 3, 6, 11, 22번과 같이 연락을 받을 수 없는 사람도 존재할 수 있다.

 

[풀이방법]

1. 비상연락망을 ArrayList를 이용하여 구현했다.

2. 노드가 몇번째에 방문되었는지를 저장하는 visited 배열을 생성했다.

3. 연락이 퍼지는 속도는 항상 일정하므로 bfs를 이용했다.

4.  시작 당번 노드를 queue에 저장, queue에서 빼낸 후 방문처리.

5. queue에서 나온 노드가 갈 수 있는 다음 노드를 순차적으로 방문, 이 때 다음 노드가 이미 방문 되었다면 그냥 넘어간다.

6. 다음 노드가 방문되지 않은 노드라면 현재 queue에서 꺼낸 노드의 방문 값 +1 을 해서 다음 노드 방문 배열에 입력해준다.

7. 방문한 노드는 queue에 넣는다.

8. queue가 빌 때 까지 5~7을 방문한다.

9. 가장 마지막에 queue에서 나온 노드의 visited값이 제일 마지막 전화이다.(maxCnt값에 저장)

10. visited 배열의 값이 maxCnt와 같은 visited 인덱스 값이 answer이 된다.

 

package A0207;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class SWEA_Contact {
	
	static List[] map;
	static int[] visited;
	static int max_cnt;
	
	static int search(int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(start);
		visited[start]=1;
		while(!queue.isEmpty()) {
			int current = queue.poll();
			for(int i=0;i<map[current].size();i++) {
				int next = (int)map[current].get(i);
				if(visited[next]!=0) continue; //방문 한 적 있으면 pass
				visited[next]=visited[current]+1; //방문 한 적 없으면 현재 방문순서 +1 해서 visited에 저장
				queue.offer(next); //방문 후 큐에 넣는다
			}
			max_cnt = visited[current]; //제일 마지막 poll 한 것이 가장 마지막 전화 받은 사람
		}
		
		return max_cnt;
	}
	public static void main(String[] args) throws Exception {
		
		System.setIn(new FileInputStream("input_contact.txt")); 
		Scanner sc = new Scanner(System.in);
		int T;
		T=10;
		
		for(int test_case=1;test_case<=T;test_case++) {
			int length = sc.nextInt();
			int start = sc.nextInt();
			max_cnt= 0;
            int answer=0;
			map = new ArrayList[101];
            visited = new int[101];
            
			for(int i=1;i<=100;i++) {
				map[i]=new ArrayList<Integer>();
			}
			
			for(int i=0;i<length/2;i++) {
				int x=sc.nextInt();
				int y=sc.nextInt();
				map[x].add(y);
			}
			int max = search(start);
			for(int i=1;i<=100;i++) {
				if(visited[i]==max) { 
					answer = i;
				}
			}
			System.out.println("#"+test_case+" "+answer);
		}
	}

}

[소감]

ArrayList와 Queue 사용법에 대해 조금 감을 잡은 것 같기도 하다. 아주 조금이지만..... bfs와 dfs를 항상 어렵게 느껴서 피해왔는데 이번 기회에 피하지 말고 맞서서 다 깨부셔야겠다.