[BOJ 3865, Java] 학회원

문제 링크

BOJ 3865

분류

너비 우선 탐색(bfs), 자료 구조(data_structures), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 해시를 사용한 집합과 맵(hash_set), 파싱(parsing), 문자열(string)

설명

최근에 마주한 코딩 테스트들에서 문자열에 관한 문제들이 자주 출제되는 경향을 보이는 거 같아 아무래도 문자열에 연관된 문제를 찾던 중 발견한 문제.

깊이 탐색을 사용하는 문제여서 아무래도 익숙했고 아직 자바 언어에 대한 숙지가 부족하다보니 풀이에 시간은 조금 걸렸지만 큰 틀은 깊이 탐색에서 벗어나지 않았다.

문자열 데이터를 잘 가공해주고 학회와 학생 이름에 대해 방문 기록 집합을 계속 체크하면서 아직 방문하지 않은 경우 각 케이스에 대해 재귀 + 카운팅 처리로 마무리할 수 있는 문제였다.

풀이 코드

import java.io.*;
import java.util.*;

public class Main {

    /**
     * 해당 학회의 총 인원수를 반환하는 함수
     */

    public static int getTotalPerson(String target) {

        // 결과값 변수 선언
        int result = 0;

        // 아직 방문하지 않은 경우에 대해서만 처리
        if (!visitLog.contains(target)) {

            // 방문 기록
            visitLog.add(target);

            // 사람이 아닌 학회일 경우
            if (clubGraph.containsKey(target)) {

                // 해당 학회의 방문하지 않은 구성원에 대해 재귀함수를 호출, 결과값에 합산
                for (String eachPerson : clubGraph.get(target)) {

                    // 구성원이 학회라면 재귀함수 호출
                    if (clubGraph.containsKey(eachPerson)) {
                        result += getTotalPerson(eachPerson);

                    // 학생이라면 아직 방문하지 않았을 경우 결과값 1 추가
                    } else {

                        if (!visitLog.contains(eachPerson)) {

                            visitLog.add(eachPerson);
                            result += 1;

                        }

                    }

                }

            }

        }

        // 결과값을 반환
        return result;

    }

    public static int strToInt(String inputString) {
        return Integer.parseInt(inputString);
    }

    // 학회 수, 첫 학회, 학회 관계 그래프, 학생 기록 집합 정적 변수 선언
    static int clubNumber;
    static String firstClub;
    static HashMap<String, ArrayList<String>> clubGraph = new HashMap<>();
    static Set<String> visitLog = new HashSet<>();

    public static void main(String[] args) throws IOException {

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        // 학회의 수 입력, 입력값이 0이라면 반복 종료
        while ((clubNumber = strToInt(input.readLine())) != 0) {

            clubGraph.clear();
            visitLog.clear();

            for (int i = 0; i < clubNumber; i++) {

                // 줄 단위 입력
                StringTokenizer clubInfo = new StringTokenizer(input.readLine(),"[:,.]");

                // 학회 이름 변수 선언
                String clubName = clubInfo.nextToken();

                // 첫 학회라면 따로 변수에 기록
                if (i == 0) {
                    firstClub = clubName;
                }

                // 기존에 없던 학회라면 추가
                if (!clubGraph.containsKey(clubName)) {
                    clubGraph.put(clubName, new ArrayList<>());
                }

                // 나머지를 전부 학회의 원소로 추가
                while (clubInfo.hasMoreTokens()) {
                    clubGraph.get(clubName).add(clubInfo.nextToken());
                }

            }

            // 함수를 호출하여 결과값을 출력 스택에 추가
            System.out.println(getTotalPerson(firstClub));

        }

    }

}