[BOJ][Python]1260번 풀이

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

1260번: DFS와 BFS

from collections import deque
import copy

def dfs(v):
    visited[v][v] = True
    print(v, end=' ')
    for i in range(1,n+1):
        if visited[v][i] == True and visited[i][i] == False:
            dfs(i)
        elif visited[i][v] == True and visited[i][i] == False:
            dfs(i)

def bfs():
    while q:
        v = q.popleft()
        print(v, end=' ')
        for i in range(1,n+1):
            if visited1[v][i] == True and visited1[i][i] == False:
                q.append(i)
                visited1[i][i] = True
            elif visited1[i][v] == True and visited1[i][i] == False:
                q.append(i)
                visited1[i][i] = True

n,m,v = map(int, input().split())
graph = [list(map(int, input().split()))for _ in range(m)]
visited = [[False for _ in range(n+1)] for _ in range(n+1)]
for i in graph:
    visited[i[0]][i[1]] = True
visited1 = copy.deepcopy(visited)
q = deque([v])
visited1[v][v] = True
dfs(v)
print('')
bfs()

오늘안에 못 올릴까봐 조마조마 했습니다만 느지막이 성공했습니다. 사실 어제까지만 해도 뭔가 감을 잘 잡은듯한 느낌이라서 빠르게 성공할 줄 알았는데 막상 이게 또 함수로 만드니까 또 다른 문제가 생기더라구요. 괜히 어떻게든 짧게 짜보겠다고 막 하다가 시간을 좀 많이 썼습니다.

 

이번에는 2차원 리스트를 만들어서 진행해봤습니다. 처음에는 1차원 리스트만 있어도 충분할 것 같았는데 엄청 조건도 많이 설정해줘야 하고 상황에 따라 정렬도 해야하고 딱 봐도 에러가 날 상황이 한 두 개가 아니더라구요. 그래서 연습도 할 겸 이차원 리스트로 진행해봤습니다. 사실 저는 인접 행렬을 이름만 들어보고 그게 뭔지는 정확히 몰랐었는데 문제를 다 풀고 나서 포스팅 작성을 위해서 찾아보니까 간선의 존재 여부를 나타내는 행렬이 인접 행렬이라고 하더라구요. 알고 사용한 것은 아니지만 저도 모르게 인접 행렬을 이용해서 문제를 풀게 되었습니다.

 

처음부터 인접 행렬을 쓰고자 했던 것은 아니었습니다. 주어지는 입력에서 간선이 항상 순서대로 풀기 쉽게 제공되지는 않았기 때문에 해당 입력을 받아서 정렬을 할지 아니면 다른 방법을 구상할지 정해야 했습니다. 그래서 정렬 외의 다른 방법을 고민하다보니 문득 간선의 관계를 2차원 리스트로 나타낼 수 있을 것 같았습니다. 어차피 방문 표시용 리스트도 필요했는데 간선의 정보는 항상 다른 노드로 주어지니까 방문 처리를 위한 주대각선은 간섭 없이 사용이 가능하겠다 싶었어요.

 

그 정도 까지 생각이 미친 다음 부터는 쉬웠습니다. 방문 처리 및 간선 표시를 위한 2차원 리스트를 만들고 연습했던 dfs와 bfs 코드를 작성했죠. 다만 이미 사용했던 방문 처리 리스트가 이미 다 True가 되었다는 사실을 깜빡했습니다. 그래서 자꾸 bfs만 제대로 출력이 안되어서 이게 왜 이러나 한참을 고민하다가 결국 리스트를 하나 더 만들었습니다만, 생각해보니 조건을 False로 변경하면 아무 문제없이 가능했습니다. 굳이 리스트를 deepcopy할 필요가 없었어요(반복문으로 주대각선만 다시 False로 변경해도 됐겠네요). 다 끝나고 나니까 더 좋은 방법들이 생각나는 건 어쩔 수 없나봅니다.

 

아무튼 이렇게 좀 오래 잡고 있었던 문제를 해결했습니다. 저난이도 bfs문제들을 착실하게 풀어온게 확실히 도움이 되는 것 같아요.