[SW expert Academy] SWEA 1238번 Contact 자바(Java)

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

문제 링크

성능 요약

메모리: 19,376 KB, 시간: 118 ms, 코드길이: 1,821 Bytes

제출 일자

2024-01-10 09:45

접근 방식

1. 배열을 통해서 인접행렬을 만들어준다.

2. visit 배열을 통해 방문 여부를 확인해준다.

3. bfs를 통해서 관련 노드 방문 처리를 해준다.

4. bfs 중 현재 연결 노드 중 최대값을 저장하여 마지막에 출력해준다.

 

1. 배열을 통해서 인접 행렬을 만들어준다. && visit 배열을 통해 방문 여부 확인

// 1 ~ 100까지 방문처리를 위한 visit 배열과 노드 연결을 위한 인접 행렬
            visit = new boolean[101];
            map = new boolean[101][101];

 

2. bfs를 통해 관련 노드를 방문 처리 && 최대값을 저장

private static int bfs(int start){
        // 출발점 넣어주기
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visit[start] = true;
        int result = 0;
        
        while(!queue.isEmpty()){
            // 현재 큐에 넣어진 사이즈 저장 후 for문 돌리기
            int len = queue.size();
            // result값 초기화
            result = 0;
            for(int l= 0; l < len; l++){
                // 현재 큐에 넣어진 사이즈(현시점에 연결된 노드 중) 최대값을 찾기
                int current = queue.poll();
                result = Math.max(result,current);
                
                for(int i = 1; i <= 100; i++){
                    // 연결이 안되거나 방문 했다면 continue
                	if(!map[current][i] || visit[i]) continue;
                
                    // 아니라면 방문 처리 후 큐에 삽입
                	visit[i] = true;
                	queue.offer(i);
                }
            }
        }
        // 최대값 리턴
        return result;
    }

 

 

전체 코드

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

class Solution{
	static boolean[][] map;
    static boolean[] visit;
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;	
		for(int tc = 1; tc <= 10; tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            // 1 ~ 100까지 방문처리를 위한 visit 배열과 노드 연결을 위한 인접 행렬
            visit = new boolean[101];
            map = new boolean[101][101];
            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());
                map[from][to] = true;
            }
           
            int result = bfs(start);
            sb.append("#" + tc + " " + result).append("\n");
		}
        System.out.println(sb);
	}
    private static int bfs(int start){
        // 출발점 넣어주기
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visit[start] = true;
        int result = 0;
        
        while(!queue.isEmpty()){
            // 현재 큐에 넣어진 사이즈 저장 후 for문 돌리기
            int len = queue.size();
            // result값 초기화
            result = 0;
            for(int l= 0; l < len; l++){
                // 현재 큐에 넣어진 사이즈(현시점에 연결된 노드 중) 최대값을 찾기
                int current = queue.poll();
                result = Math.max(result,current);
                
                for(int i = 1; i <= 100; i++){
                    // 연결이 안되거나 방문 했다면 continue
                	if(!map[current][i] || visit[i]) continue;
                
                    // 아니라면 방문 처리 후 큐에 삽입
                	visit[i] = true;
                	queue.offer(i);
                }
            }
        }
        // 최대값 리턴
        return result;
    }
}

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy