[프로그래머스][Python][Lv. 2] 바이러스 파이프

1. 문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/468373

---

2. 제한 사항

---

3. 입출력 예

---

4. 풀이

from itertools import product 

def solution(n, infection, edges, k):
    answer = 0
    
    # 파이프 열기 순서 경우의 수
    all_pipe_cases = list(product([1, 2, 3], repeat=k))
    
    # 연결된 배양체 리스트 생성
    graph = [[] for _ in range(n + 1)]
    for edge in edges:
        start, end, p_type = edge
        graph[start].append((end, p_type))
        graph[end].append((start, p_type))
    
    # 파이프 열었다 닫는 모든 조합 계산
    for case in all_pipe_cases:
        # 감염된 배양체 집합 생성
        infected = set([infection])
        
        # 타입 순서대로 열었다 닫기 반복
        for p_type in case:
            stack = list(infected)
            
            # 연속된 타입 파이프도 처리하도록 반복 수행
            while stack:
                inf = stack.pop();
                for (n_num, n_p_type) in graph[inf]:
                    if p_type == n_p_type and n_num not in infected:
                        infected.add(n_num)
                        stack.append(n_num)
        
        # 감염된 배양체 집합 수와 정답 비교해서 큰 값을 정답으로 설정
        answer = max(answer, len(infected))
    
    return answer

---

5. 후기

연결된 배양체를 만들고 재귀로 돌면서 처리해도 좋지만 그냥 단순히 이렇게 해버리면 연속으로 같은 타입의 파이프가 있으면 가까운 1개만 처리가 되고 다른 것들은 누락이 된다. 입출력 예 2번에서 확인할 수 있다.

 

그러면 미리 파이프 여는 순서를 정해놓고 그 안에서 연결된 배양체를 확인할 때 재귀 처리를 하면 된다. 나는 재귀 함수를 만드는 것 대신 스택을 활용한 반복문을 사용했다.

 

이번 문제를 풀면서 아직 파이썬이 익숙치 않아서 여러가지로 찾아봤는데 itertools를 활용하면 여러 유용한 기능들을 사용할 수 있다는 것을 알았다. 이 문제에서도 가능한 모든 조합을 찾는데 유용하게 활용했다. 사실 완전히 최적화하려면 1, 1 이런식으로 연속으로 같은 파이프를 열고 닫는 경우는 제외해야겠지만 제한사항을 보니 그냥 풀어도 통과할거 같아서 제출했더니 통과했다.

 

지금까지는 거의 문법 공부용으로 문제를 활용했는데 사실 코딩테스트 문제가 문제 해결 능력과 알고리즘 활용을 평가하려는 목적이기 때문에 난이도가 높아질수록 좀 더 머리 쓰는 연습을 해야되겠다고 생각했다. 이 문제도 머리가 잘 안 돌아가서 답을 가르쳐달라고 한건 아니지만 제미나이에게 내 생각을 말하고 평가받는식으로 진행해봤다. 예전에 몇 시간동안 고민해도 안 풀리는 문제도 있었는데 그럴 때는 이처럼 답 자체를 알려달라는게 아닌 내 생각이 잘못된건지 분석하게 시키고 공부하는게 더 나은거 같다.