백준 2606번 - 바이러스
백준 2606번 바로가기 나의 풀이 vertexList = [i for i in range(int(input()))] edgeList = [] for _ in range(int(input())): a,b=map(int,input().split()) edgeList.append((a,b)) edgeList.append((b,a)) adjacencyList = [[] for vertex in vertexList] for edge in edgeList: adjacencyList[edge[0]-1].append(edge[1]) stack = [1] visitedVertex = [] while stack: current = stack.pop() if current not in visitedVertex: visitedVertex.append(current) stack += adjacencyList[current-1] print(len(visitedVertex)-1) CODE REVIEW 백준에서 그래프 이론의 문제를 풀기 시작했다. 기본적인 DFS와 BFS부터 공부했는데, 이론은 쉬운데 구현하려니까 은근 복잡했다. 2606번 문제에서 주의할 점은 간선(Edge)이 방향성이 없다는 점이다. 처음에 자꾸만 답에 오류가 발생하길래 이유를 찾아봤더니, edgeList를 만드는 과정에서 (a,b)는 고려했지만 (b,a)를 고려하지 못했기 때문이라는 것을 깨달았다. 이 풀이에서는 list을 이용해서 graph를 나타냈는데, adjacencyList를 불러올 때에 인덱스가 1씩 밀리는걸 고려해주어야해서 매우 골치아프다. 다음에는 dictionary 형태로 만들어서 Vertex(정점,Node) 번호만 알면 바로 구할 수 있게 구현해볼 계획이다. 깊이우선탐색(DFS, Depth First Search) 에 대해 아주 잘 설명된 영상 ...