본문 바로가기

dfs4

[python] 11725번 - 트리의 부모 찾기 문제 파이썬 풀이 트리를 그래프를 저장하듯 리스트 형태로 저장하고, 부모 노드를 저장하는 리스트를 생성하는 것이 포인트였다. 부모 노드를 저장하는 리스트는 리스트의 인덱스가 해당 노드가 되고 저장된 값은 부모 노드가 된다. 예를 들어보면 2와 연결되어있는 노드 들은 2의 부모 노드와 자식 노드로 나뉜다. 이때 부모 노드를 저장하는 리스트에서 2의 부모 노드가 무엇인지 가져와 2와 인접한 노드들 중 부모 노드를 제외한다. 그럼 나머지는 전부 2의 자식노드가 된다. 이제 자식 노드로 구별된 노드들의 부모 노드를 2로 저장한다. 이와 같은 과정을 모든 노드들에 접근하면서 부모 노드를 저장한다. 모든 노드들을 접근하는 과정에서는 dfs나 bfs를 이용하여 전체 탐색한다. 나는 dfs를 통해 구현하였다. from.. 2021. 12. 20.
[python] 2667번 - 단지번호붙이기 문제 파이썬 풀이 2차원 리스트에서의 탐색은 어떤 식으로 해야 하는지 이해하는데 조금 어려웠었다. 여기서의 포인트는 탐색할 방향인 상하좌우를 이동 좌표를 리스트에 담아 for문을 통해 탐색을 진행하는 것이다. 그리고 탐색의 방법도 dfs를 통해 재귀로 탐색하였다. 좌표 리스트 dx=[-1,0,1,0] dy=[0,1,0,-1] 해당 좌표는 dx, dy에서 같은 인덱스끼리 묶어보면 (-1, 0), (0, 1), (1, 0), (0, -1)로 각각 좌(x축으로 -1 이동), 상(y축으로 +1 이동), 우(x축으로 +1 이동), 하(y축으로 -1 이동)를 의미한다. DFS 탐색 함수 def dfs(x,y) : global cnt matrix[x][y] = "0" #방문한 곳 0으로 만들기 cnt+=1 #카운트 .. 2021. 12. 8.
[python] 2606번 - 바이러스 문제 파이썬 풀이 이 문제는 1번부터 연결되어있는 모든 노드를 탐색하는 문제이다. dfs와 bfs 내용 공부를 할 때 전체 탐색에 있어서는 dfs를 사용한다는 내용이 떠올라 dfs를 적용시켜 문제를 풀었다. 앞에 1260번 문제에서 이미 기본적인 dfs와 bfs를 구현했던 터라 코드 내용을 조금만 바꾸면 돼서 쉽게 풀 수 있었다. import sys input = sys.stdin.readline e = int(input().rstrip()) v = int(input().rstrip()) graph = [[0]*(e+1) for _ in range(e+1)] visited = [0] *(e+1) def dfs(node) : visited[node] = 1 for i in range(1, e+1) : if.. 2021. 12. 7.
[python] 1260번 - DFS와 BFS 문제 파이썬 풀이 이 문제는 기본적인 dfs, bfs를 구현하여 결과를 출력하는 문제이다. 우선 그래프는 인접 행렬 방식으로 구현을 하였다. 각종 변수 초기화 n, m, v = map(int, input().rstrip().split()) graph = [[0]*(n+1) for _ in range(n+1)] visited_bfs = [0] * (n+1) visited_dfs = [0] * (n+1) graph에서 n+1을 한 이유는 인덱스는 0부터 시작이어서 1부터 시작하는 숫자와 인덱스를 매칭 시키기 위해 1개를 더 생성한 것이다. visited배열들은 해당 인덱스에 해당하는 숫자를 방문했는지 여부를 기록할 리스트이다. (방문 x : 0, 방문 o : 1) 즉 예를 들어 2라는 숫자의 노드를 방문했다.. 2021. 12. 7.

티스토리툴바