1238번 - Contact

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간
4. 우리 반 1등 코드와의 차이

 

 

 

---

 

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

BFS 탐색을 하는 문제이다.

시작점에서 가장 마지막으로 연락받으면서 + 숫자가 가장 큰 값을 리턴하면 된다.

 

문제에서 주어진 입력을 읽어보면 {from, to} 쌍이 여러 번 반복돼서 들어오는 경우도 있다고 한다.

처음에는 입력받을 때 중복제거하는 로직을 사용했었는데

visited 기록한다면 중복제거를 따로 처리해주지 않아도 된다.

또, 문제의 예제처럼 7 -> 1과 1 -> 7이 입력되는 경우 또한 visited가 있으면 따로 처리하지 않아도 된다.

 

입력 데이터를 처리하는 방법은 [1267번 - 작업순서] 문제와 동일하기 때문에 링크를 확인해보면 된다.

 

 

2. 코드

public class Day6_1238_Contact {
	static final int N = 100;
	static boolean[] visited;
	public static int[][] load;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		for (int tc = 1; tc <= 10; tc++) {
			load = new int[N + 1][N + 1];
			visited = new boolean[N + 1];
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			st.nextToken(); // 데이터의 길이 (필요없음)
			int start = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine(), " ");
			while (st.hasMoreTokens()) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				
				load[from][0]++; // 개수 증가
				load[from][load[from][0]] = to; // 다음 정점의 위치 저장
			}
			
			sb.append("#" + tc + " " + BFS(start) + "\n");
		}
		System.out.println(sb.toString());
	}
	
	public static int BFS(int from) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(from);
		visited[from] = true;
		int[] depth = new int[N + 1];
		depth[from] = 1; // 첫 시작하는 곳은 깊이가 1
		
		// 본격적인 BFS 탐색 시작
		while(!queue.isEmpty()) {
			from = queue.poll();
			
			for (int i = 1; i <= load[from][0]; i++) {
				if(!visited[load[from][i]]) {
					queue.add(load[from][i]);
					visited[load[from][i]] = true;
					depth[load[from][i]] += depth[from] + 1; // 깊이 기록
				}
			}
		}
		
        // 저장된 깊이들 중 가장 큰 값 찾기
        int idx = 1;
        for(int i=1; i<=N; i++) {
            if(depth[i] >= depth[idx]) {
                idx = i;
            }
        }
         
        return idx;
	}
}

몇 번째로 연락을 받는지는 depth 배열을 사용해서 구할 수 있었다.

 

 

3. 실행시간

실행결과

 

첫 번째 시도 후 1위를 탈환하고 싶어 재도전했지만

1등의 자리는 너무나 높았다고 한다.

 

 

4. 우리반 1등 코드와의 차이

여태까지는 다른 사람의 코드를 열람하면 포인트도 깎이고 내 자존심도 깎이기 때문에 열람해보지 않았는데

그래도 한 번쯤은 보고 배우는 게 좋지 않을까 싶어서 대체 저 3ms의 차이가 무엇인지 알아봤다.

내 코드가 아니니까 코드를 올릴 수는 없고 텍스트로 설명을 하자면...

 

• 데이터를 저장하는 방식을 배열이 아닌 리스트를 사용했다.
• 테스트 케이스 반복문을 for가 아닌 while을 사용했다.
• StringTokenizer를 사용할 때 구분자를 주지 않았다.
  • " "는 기본 구분자라 넣어주지 않아도 됐었다.
  • 기본 구분자: \t, \n, \r
• visited를 사용하지 않고 depth 배열의 값이 초기값인지를 판단해 방문 여부를 따졌다.
• 멤버 변수로 뺄 수 있는 건 최대한 다 빼냈다.
  • 멤버 변수가 아니어도 상관없는 (메인 문에서만 사용되는) 변수도 다 빼냈는데 이 이유는 잘 모르겠다.

 

의미가 있는 차이는 이정도 있는 것 같았다.

이 중에서 visited가 꼭 필요하지 않았다는 점이 놀라웠고 3ms 차이가 난 주요 원인이 되지 않았나 싶다.

 

 

 

 

 

---

💡 느낀 점

• DFS를 스택과 재귀로 구현할 수 있으니 BFS도 큐와 재귀로 구현할 수 있을 거라 생각했는데 아니었다. 덕분에 삽질 많이 함
• 우리 반 1등의 코드에서 많은 걸 배울 수 있었고 포인트 깎인 게 아쉽지 않았다!
• StringTokenizer에 구분자 안 넣어도 됐다는 사실은 좀 충격적... 이걸 모르고 살았네...
• visited가 없어도 된다는 아이디어는 앞으로도 잘 써먹을 수 있을 것 같다.

---