[SWEA][BFS][Java] 1238. Contact : D4

문제 링크 : https://swexpertacademy.com/main/code/problem/problemSubmitHistory.do?contestProbId=AV15B1cKAKwCFAYD

 

이 문제는 연락이 시작된 사람으로부터 연결된 사람들에게 순차적으로 연락이 전달될 때, 가장 마지막에 연락을 받는 사람 중 번호가 가장 큰 사람을 찾는 문제이다. 연락 관계는 방향 그래프로 볼 수 있기 때문에 시작점에서부터 BFS(너비 우선 탐색) 를 이용해 탐색하면 자연스럽게 해결할 수 있다!! 

 

총 문제 풀이 시간은 42분이 걸렸는데, 중간에 ArrayList 초기화를 안시켜줘서 계속 Runtime Error 떠서 아주 F앙당했음.

 

ArrayList 꼭 초기화 해주자... 메모... 📝

 

처음 구현에서는 각 노드마다 현재 연락 단계(cnt) 를 함께 저장하기 위해 Node 클래스를 만들어 (번호, cnt) 형태로 큐에 넣어 탐색했다. 그리고 탐색하면서 가장 깊은 단계와 그 단계에서 가장 큰 번호를 비교하며 결과를 갱신하는 방식으로 구현했다. 기능적으로는 문제가 없었지만, 코드가 길어지고 불필요한 객체 생성이 많아지는 단점이 있었다. 굳이 필요 없는 칭구..

 

이를 개선하기 위해 BFS의 레벨 탐색 구조를 활용하도록 코드를 수정했다. BFS에서는 한 번의 반복이 동일한 cnt에 해당하는 노드들을 의미하기 때문에, queue.size()를 이용해 현재 레벨에 있는 노드들을 한 번에 처리할 수 있다. 이렇게 하면 cnt를 따로 저장할 필요가 없어지고 Node 클래스도 제거할 수 있다.

개선된 방식에서는 큐에서 현재 레벨의 모든 노드를 꺼내면서 그 중 가장 큰 번호를 기록한다. 그리고 다음 레벨 탐색이 끝나면 그 값이 자연스럽게 가장 마지막에 연락받은 사람들 중 가장 큰 번호가 된다. 이 방법을 사용하면 cnt 비교 로직도 사라지고 코드 구조도 훨씬 단순해진다.

 

비슷한 문제를 풀 때 늘 방문 횟수를 저장했는데,, 이런 방법도 있다니,, 코딩의 끝은 어디인가ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ... 

최종 코드

import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;

import java.util.*;
class Solution
{
	public static void main(String args[]) throws Exception
	{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= 10; test_case++)
		{
            sb.append("#").append(test_case).append(" ");
            
            st = new StringTokenizer(br.readLine());
            int L = Integer.parseInt(st.nextToken());
            int S = Integer.parseInt(st.nextToken());
            
            List<Integer>[] contacts = new ArrayList[101];
            for(int i = 1; i <= 100; i++){
            	contacts[i] = new ArrayList<>();
        	}
            
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < L/2 ; i++){
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                contacts[from].add(to);
            }
            
            boolean[] visited = new boolean[101];
            Queue<Integer> q = new LinkedList<>();
            
            visited[S] = true;
            q.add(S);
            
            int result = S;
            
            while(!q.isEmpty()){
                int size = q.size();
                int max = 0;

                for(int i = 0; i < size; i++){
                    int cur = q.poll();
                    max = Math.max(max, cur);
                    
                    for(int next : contacts[cur]){
                        if(visited[next]) continue;
                        
                        visited[next] = true;
                        q.add(next);
                    }
                }
                    result = max;
            }
             sb.append(result).append("\n");
		}
        System.out.print(sb);
	}
}

 

 

 

불필요한게 아주 많은 나의 코드

import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;

import java.util.*;
class Solution
{
	public static void main(String args[]) throws Exception
	{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= 10; test_case++)
		{
            sb.append("#").append(test_case).append(" ");
            st = new StringTokenizer(br.readLine());
            int L = Integer.parseInt(st.nextToken());
            int S = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            List<Integer>[] contacts = new ArrayList[101]; 
            
            for(int i = 1; i <= 100; i++){
            	contacts[i] = new ArrayList<>();
        	}
            
            for(int i = 0; i < L/2 ; i++){
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                contacts[from].add(to);
            }
            
           Queue<Node> q = new LinkedList<>();
            q.add(new Node(S, 0));
            boolean[] visited = new boolean[101];
            visited[S] = true;
            
            int max = Integer.MIN_VALUE;
            int result = -1;
            
            while(!q.isEmpty()){
                Node cur = q.poll();
                int cur_contact = cur.contact;
                if(max == cur.cnt) result = Math.max(result, cur_contact);
                else if(max < cur.cnt){
                    result = cur_contact;
                    max = cur.cnt;
                }
                
                for(int c : contacts[cur_contact]){
                    if(visited[c]) continue;
                    
                    q.add(new Node(c, cur.cnt+1));
                    visited[c] = true;  
                }  
            }
             sb.append(result).append("\n");
		}
        System.out.print(sb);
	}
    public static class Node{
        int contact, cnt;
        public Node(int contact, int cnt){
            this.contact = contact;
            this.cnt = cnt;
        }
    }
}