99클럽 코테 스터디 11일차 TIL: 골드 너비 우선 탐색

오늘의 문제: 25195. Yes or yes

오늘 문제는 보자마자 큰일 났다는 생각이 제일 먼저 들었다. 그래프 관련된 문제 중 골드4면 꽤나 어려울 거라 생각해서 약간 시간을 잡아먹겠다는 생각이 들었다. 그래봤자 크게 어렵지 않겠지라는 생각으로 우선 풀어봤다.

아이디어: 곰곰이를 만나지 않고 종료되면 틀리지 않을까.

그래프 탐색을 종료하는 방법에 대해서 생각을 해봤을 때, (1) 곰곰이를 만나게 되면 그 경로는 앞으로 검사하지 않는다. (2) 곰곰이를 만나지 않고 경로 탐색이 종료될 경우 답은 yes가 된다.

라는 대원칙을 가지고 시작해보려 한다.

from collections import deque
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
graph=[[] for i in range(n+1)]
visit=[-1 for i in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)

fan_count=int(input())
fan_list=map(int,input().split())

for i in fan_list:visit[i]=1

def bfs(graph, start):
    deq=deque()
    deq.append(start)
    flag=0
    
    while deq:
        node=deq.popleft()
        if visit[node]==1: continue
        else:
            if graph[node]==[]: flag=1
            else:
                for i in graph[node]: deq.append(i)
    print(["Yes","yes"][flag])

bfs(graph,1)

진짜 놀랍게도 한번의 실수도 없이 바로 해결했다. 아무래도 아이디어에 허점이 없었던 듯하다. 곰곰이를 만나면 넘기고, 만나지 않고 끝을 만나면 실패한 것으로 간주하는 아이디어가 정답이었던 것이다.

오늘의 회고

오늘은 생긴거에 비해 크게 어려운 문제가 아니였다. 심지어 BFS 코드는 어느정도 적응했는데 BFS로 별 문제없이 풀려서 더 편했던 듯하다. 골드라고 해서 쫄지 말고 우선 코드 짜면서 생각해보는 것도 괜찮아보인다.

며칠 연속으로 그래프를 계속 풀다보니 그래프에 대한 자신감이 붙고 있다. 솔직히 이대로 골드 하위 문제들만 꾸준히 풀어도 충분히 플레티넘으로 승급하지 않을까…?하는 생각이 조금 든다. 앞으로도 꾸준히 문제를 풀어보자…