[5문제] DFS 문제 풀이 01

m1njae·2022년 2월 27일
0

5문제

목록 보기
13/14
post-thumbnail

백준 2606번

해결 아이디어

깊이 우선 탐색을 통해서 노드를 방문해준다. 노드를 방문해줄 때마다 방문 횟수를 1씩 증가시켜준다. 인덱스를 구별하기 쉽게 인덱스 0은 빈칸으로 비워두었다.

내가 작성한 코드

n = int(input())
connect = int(input())
graph = [[] for i in range(n+1)]

count = 0
def dfs(graph,start,visited):
    global count
    visited[start] = True

    for i in graph[start]:
        if not visited[i] :
            dfs(graph,i,visited)
            count+=1
            
for i in range(connect):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (n+1)
dfs(graph,1,visited)
print(count)

백준 11724번

해결 아이디어

연결 요소의 개수를 구하는 문제였다. 예제 입력 1에서는 1,2,5가 3개의 간선으로 연결되어 있고, 3,4,6이 2개의 간선으로 연결되어 있으므로 예제 입력 1의 연결 요소는 2개이다. 이처럼 깊이 우선 탐색을 통해서 정점을 방문해준다. 이때, 연결 요소를 구해야하므로 반복문을 통해서 주어진 모든 정점을 확인해준 후, 방문 처리가 되지 않을 때만 숫자를 세주면 된다.

내가 작성한 코드

import sys
sys.setrecursionlimit(10000)

n, m = map(int, sys.stdin.readline().split())

lst =[[] for _ in range(n+1)]
visited = [False for _ in range(n+1)] 
count = 0

def dfs(start):
    visited[start] = True
    
    for i in lst[start]:
        if not visited[i]:
            dfs(i)
            
for _ in range(m):
    a,b = map(int, sys.stdin.readline().split())
    lst[a].append(b)
    lst[b].append(a)

for j in range(1, len(visited)):
    if not visited[j]:
        dfs(j)
        count+=1

print(count)

백준 1260번

해결 아이디어

DFS와 BFS를 구현하는 문제였다.

내가 작성한 코드

from collections import deque

def dfs(graph,v,visited):

    visited[v] = True
    print(v, end= " ")

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

def bfs(graph,start,visited):
    queue = deque([start])

    visited[start] = True

    while queue:

        v = queue.popleft()
        print(v, end =' ')

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    

n,m,v = map(int,input().split())
graph = [[] for i in range(n+1)]
visited = [False]* (n+1)

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

for i in range(1, n+1):
    graph[i].sort()

dfs(graph,v, visited)
visited = [False]* (n+1)
print()
bfs(graph,v,visited)

백준 4963번

해결 아이디어

고민하는 데 오랜 시간이 걸리기도 하였고, DFS의 응용에서 처음 보는 유형이어서 타인의 풀이를 참고했다. DFS와 같은 개념이었지만, 간선을 통해 연결되는 것이 아닌 상하좌우, 대각선의 방향을 설정해주어야 했다. 또한 지도의 너비와 높이가 정해져 있기 때문에 지도의 범위에서 벗어나지 않도록 조건을 지정해주어야한다.

코드

import sys
sys.setrecursionlimit(10000)

def dfs(x,y):
    dx = [1,1,-1,-1,1,-1,0,0]
    dy = [0,1,0,1,-1,-1,1,-1]

    graph[x][y] = 0
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:
            dfs(nx,ny)

while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0:
        break
    graph = []
    count = 0
    for i in range(h):
        graph.append(list(map(int, sys.stdin.readline().split())))

    
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                dfs(i,j)
                count +=1

    print(count)

백준 11725번

해결 아이디어

깊이 우선 탐색을 통해서 노드를 방문 처리하는 과정이 동일하다. 하지만 각 노드의 부모를 구해주어야 한다. 각 노드의 부모는 방문 처리하기 전의 노드들이다. 재귀 함수를 통해서 방문되지 않는 노드를 도는 과정에서 0으로 초기화되어 있는 visited 리스트에 부모 노드를 담아준다.

내가 작성한 코드

import sys
sys.setrecursionlimit(10**9)

n = int(input())

graph = [[] for _ in range(n+1)]

def dfs(start):
   for i in graph[start]:
       if visited[i] == 0:
           visited[i] = start 	 ## 부모 노드를 담아주는 과정
           dfs(i)
             
for i in range(n-1):
   a,b = map(int,input().split())
   graph[a].append(b)
   graph[b].append(a)

visited = [0] * (n+1)
dfs(1)
for i in range(2,n+1):
   print(visited[i])
profile
할 수 있는 것부터 차근차근, 항해자의 공부 기록공간

0개의 댓글