[ 백준 ] 9466 팀 프로젝트

Link | 백준 9466번 문제 팀 프로젝트

📌 About

DFS으로 해결할 수 있는 문제이다.

다만, 다음으로 탐색하는 영역의 상태에 따라 어떤 처리를 할 것인지 결정해야 한다.

📌 Solution

상태는 다음과 같이 4가지가 있다.

DEFAULT : 어떠한 작업도 하지 않은 상태

SEARCHING : 현재 DFS를 통해 탐색한 상태

TEAMED : 팀으로 묶인 상태

NON_TEAMDED : 팀으로 묶일 수 없는 상태

1번부터 N번까지 탐색하면서 DEFAULT 상태이면 DFS를 시작한다.

IntStream.rangeClosed(1, NUM).filter(num -> states[num] == State.DEFAULT)
                    .forEach(num -> search(num, new ArrayList<>()));

탐색을 할 때는 2가지 정보를 재귀적으로 제공해야 한다.

하나는 현재 탐색하는 번호이고 다른 하나는 지금까지 탐색한 번호들의 탐색 순서이다.

search(int num, List<Integer> searchList)

탐색을 할 때는 우선 탐색 리스트에 탐색 번호를 추가한다.

또한 상태를 SEARCHING으로 변경하고 다음 탐색 번호의 상태를 가져온다.

searchList.add(num);
states[num] = State.SEARCHING;
State state = states[prefers[num]];

만약 다음 탐색 번호의 상태가 SEARCHING이면 사이클을 형성한다는 것이다.

사이클은 다음 탐색 번호 -> 현재 번호 순서로 형성된다.

즉, 1 -> 3 -> 4 -> 5 -> 3 이면 3, 4, 5가 사이클을 형성하고 팀으로 묶인다.

1은 팀을 이루지 못하는 상태가 된다.

if (state == State.SEARCHING) {
    int cycleIdx = searchList.indexOf(prefers[num]);
    searchList.subList(0, cycleIdx).forEach(no -> states[no] = State.NON_TEAMED);
    searchList.subList(cycleIdx, searchList.size()).forEach(no -> states[no] = State.TEAMED);
}

만약 다음 탐색 번호의 상태가 TEAMED 아니면 NON_TEAMED이면 사이클을 이루지 못한다.

그렇기 때문에 현재까지의 탐색 번호들의 상태를 NON_TEAMED으로 변경한다.

if (state == State.TEAMED || state == State.NON_TEAMED)
	searchList.forEach(no -> states[no] = State.NON_TEAMED);

다음 탐색 번호가 아직 DEFAULT이면 재귀적으로 DFS를 수행한다.

if (state == State.DEFAULT) search(prefers[num], searchList);

최종적으로 TEAMED 상태가 아닌 번호들의 개수를 출력한다.

IntStream.rangeClosed(1, NUM).filter(num -> states[num] != State.TEAMED).count();

📌 Code

GitHub Repository

private int[] prefers;
private State[] states;

public void solve() throws IOException {
    int T = Integer.parseInt(reader.readLine());
    while (T-- > 0) {
        int NUM = Integer.parseInt(reader.readLine());
        prefers = Arrays.stream(("0 " + reader.readLine()).split(" "))
                .mapToInt(Integer::parseInt).toArray();
        states = Stream.generate(() -> State.DEFAULT).limit(NUM + 1).toArray(State[]::new);
        IntStream.rangeClosed(1, NUM).filter(num -> states[num] == State.DEFAULT)
                .forEach(num -> search(num, new ArrayList<>()));
        result.append(IntStream.rangeClosed(1, NUM)
                        .filter(num -> states[num] != State.TEAMED)
                .count()).append("\n");
    }
}

private void search(int num, List<Integer> searchList) {
    searchList.add(num);
    states[num] = State.SEARCHING;
    State state = states[prefers[num]];
    if (state == State.SEARCHING) {
        int cycleIdx = searchList.indexOf(prefers[num]);
        searchList.subList(0, cycleIdx).forEach(no -> states[no] = State.NON_TEAMED);
        searchList.subList(cycleIdx, searchList.size()).forEach(no -> states[no] = State.TEAMED);
    } else if (state == State.TEAMED || state == State.NON_TEAMED)
        searchList.forEach(no -> states[no] = State.NON_TEAMED);
    else if (state == State.DEFAULT) search(prefers[num], searchList);
}