<SWEA> #1238_Contact java

SWEA #1238

✏️1. Solution

비상 연락망이 주어질 때 가장 나중에 연락을 받게 되는 사람 중 번호가 가장 큰 사람을 고르는 문제다. 이때 연락은 인접한 모든 곳에 동시에 주어진다.

그림과 같이 가운데 1이라고 적힌 부분에서 연락이 시작된다고 하면 오른쪽 각 칸에 적힌 순서대로 연락이 동시에 가게 되고 빨간색 칸에 있는 부분이 마지막으로 동시에 연락이 가는 곳 -> BFS 이용

✏️2. StringTokenizer

정의

BufferedReader 클래스의 메서드로 입력을 읽으면, 라인 단위로 읽게 된다
그래서 특정 기준으로 문자열을 분리하는데 StringTokenizer가 필요

구현

import java.util.StringTokenizer;

StringTokenizer st1=new StringTokenizer(문자열); // 띄어쓰기 기준으로 문자열 분리
StringTokenizer st2=new StringTokenizer(문자열, 구분자); // 구분자를 기준으로 문자열 분리
StringTokenizer st3=new StringTokenizer(문자열, 구분자, true/false); 
// 구분자를 기준으로 문자열을 분리할 때 구분자도 토큰으로 넣을지 (true) 
//구분자는 분리된 문자열 토큰에 포함 안 시킬지 (false) 
// default=false

e.g.

문제에서 입력은 다음과 같이 주어진다
첫 줄엔 입력받는 데이터의 길이, 시작점
다음 줄에는 {from, to, from, to ...}의 형태로 주어진다

24 2
1 17 3 22 1 8 1 7 7 1 2 7 2 15 15 4 6 2 11 6 4 10 4 2

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;

st=new StringTokenizer (br.readLine(), " ");
//BufferedReader로 문자열을 입력 받는데 공백을 기준으로 읽어들이겠다

int N=Integer.parseInt(st.nextToken());
start=Integer.parseInt(st.nextToken());

st=new StringTokenizer (br.readLine(), " ");
for (int i=0; i<N/2; i++) {
	int from=Integer.parseInt(st.nextToken());
	int to=Integer.parseInt(st.nextToken());
}

✏️3. BFS

• boolean[] visited를 두어 해당 노드가 방문 된 적이 있는지 저장
• Queue를 사용하여 방문한적 없고, 해당 노드에 인접한 노드를 차례대로 넣고 방문한다
• 문제에서 마지막으로 동시에 방문되는 노드에서 제일 큰 값을 찾아야 하므로 현재 queue의 size를 저장하는 변수를 두어 같은 레벨에 있는 노드 중에서 최대값을 매번 갱신한다

	private static int bfs() {
		int ret=0;
		
		boolean[] visited=new boolean[MAX];
		
		Queue<Integer> q=new LinkedList<>();
		q.offer(start);
		visited[start]=true;
		
		while (!q.isEmpty()) {
			
			int size=q.size();
			int maxNode=0;
			
			while (--size>=0) {
				int cur=q.poll();
				for (int i=1; i<MAX; i++) {
					if (adj[cur][i] && !visited[i]) {
						q.offer(i);
						maxNode=Math.max(maxNode,i);
						visited[i]=true;
					}
				}
				if (maxNode>0) ret=maxNode;
			}
		}
		return ret;
	}

✏️4. Source Code

package org.swea.eclipse;

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


public class Solution {

	public static final int MAX=101;
	
	static boolean [][]adj;
	static int start;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		
		for (int tc=1; tc<=10; tc++) {
			st=new StringTokenizer (br.readLine(), " ");
			int N=Integer.parseInt(st.nextToken());
			start=Integer.parseInt(st.nextToken());
			
			adj=new boolean[MAX][MAX];
			
			st=new StringTokenizer (br.readLine(), " ");
			for (int i=0; i<N/2; i++) {
				int from=Integer.parseInt(st.nextToken());
				int to=Integer.parseInt(st.nextToken());
				adj[from][to]=true;
			}
			int ret=bfs();
			
			System.out.println("#"+tc+" "+ret);
		
		}

	}
	
	private static int bfs() {
		int ret=0;
		
		boolean[] visited=new boolean[MAX];
		
		Queue<Integer> q=new LinkedList<>();
		q.offer(start);
		visited[start]=true;
		
		while (!q.isEmpty()) {
			
			int size=q.size();
			int maxNode=0;
			
			while (--size>=0) {
				int cur=q.poll();
				for (int i=1; i<MAX; i++) {
					if (adj[cur][i] && !visited[i]) {
						q.offer(i);
						maxNode=Math.max(maxNode,i);
						visited[i]=true;
					}
				}
				if (maxNode>0) ret=maxNode;
			}
		}
		return ret;
	}
}