백준 온라인 저지 1260: DFS와 BFS

NameError·2021년 4월 29일

문제 링크

https://www.acmicpc.net/problem/1260

풀이 전 계획과 생각

이 문제를 처음 보았을 때는 DFS와 BFS에 대해서 정말 아무것도 몰랐기 때문에 다른 문제부터 풀어보면서 익숙해져야겠다고 생각했다. 그래서 데이터가 2차원이 아니라 1차원이라는 점 때문에 비교적 쉽게(???) 느껴졌던 1697번 숨바꼭질부터 풀고 돌아왔다.

문제 풀이의 계획은 다음과 같다.

정점의 개수 N, 간선의 개수 M, 시작하는 정점 좌표 V를 입력받는다.
(N+1) x (N+1)의 2차원 배열 n을 만들고 모든 값은 0으로 한다. (NxN으로 만들면 0부터 시작해서 N-1에서 끝나는데 일일이 좌표에서 -1을 하지 않을 거라서 0행과 0열은 버리는 걸로)
간선들의 값을 입력받으면서 위의 2차원 배열 n에서 해당되는 정점의 좌표에 1이 대응되도록 인접행렬로 만든다.
DFS 함수(입력 매개변수: 현재 시작점 V, 인접행렬 n, 방문 경로를 담은(시작할 때에는 비어 있는) 배열 route[])
- 현재 시작점을 route[]에 담고 출력한다
- 인접행렬에서 반복문: 예를 들어 현재 정점이 3이라면 1,2,4,...N 중에서 어디로 갈지 정해야 한다. 그렇다면 인접행렬에서 (3,i)가 연결되었는지, 그리고 이전에 방문하지 않았는지(배열 route[]에 있다)를 판정하여 아니면 다음 간선을 찾고 맞으면 i를 다음 시작점으로 하여 재귀시킨다.
BFS 함수(입력 매개변수: 현재 시작점 V, 인접행렬 n)
- 현재의 방문 예정 정점들을 담은 배열 v[]에는 V만 있다
- 방문한 곳들을 기록하는 배열 route[]는 비어 있다
- v[]가 빈 배열이 될 때까지 다음을 반복한다.
  - 현재 정점을 v[]에서 left pop한다
  - route[]에 right push 한다
  - 여기에서 1부터 N까지 인접행렬에서 비교하는데...
  - i가 route[]에 없고(아직 방문하지 않았고) v[]에 없고(이걸 안 넣으면 오류가 떴는데 왜인지는 솔직히 헷갈린다) 인접행렬 n[]에서 (현재정점, i)가 1이면 다음 예상 정점 목록인v[]에 right push한다.
  - 이렇게 하면 예를 들어 현재 정점이 1이고 연결되는 점이 2,3,4이고 2에서는 5,6, 3에서는 7,8, 4에서는 9,10이 연결된다면 v[]에 2,3,4,5,6,7,8,9,10... 순서대로 들어가서 앞에서부터 하나씩 처리하게 될 것이다.

풀이 (코드 블록 첨부)

import sys
N,M,V=map(int,sys.stdin.readline().split())

def dfs(s,arr,route):
    route.append(s)
    print(s,end=" ")
    
    for x in range(1,len(arr)):
        if arr[s][x]==1 and x not in route:
            dfs(x,arr,route)


def bfs(s,arr):
    to_visit=[s]
    route=[]
    while to_visit!=[]:
        current = to_visit.pop(0)
        route.append(current)
        for x in range(1,len(arr)):
            if x not in route and x not in to_visit and arr[current][x]==1:
                to_visit.append(x)
    
    print(" ".join(str(element) for element in route))

paths=[[0]*(N+1) for x in range(N+1)]

for i in range(M):
    n=list(map(int,sys.stdin.readline().split()))
    
    
    
    paths[n[0]][n[1]]=1
    paths[n[1]][n[0]]=1
dfs_route=[]
dfs(V,paths,dfs_route)

print()
bfs(V,paths)