내 풀이
n = int(input())
x, y = map(int, input().split())
m = int(input())
data = [[] for _ in range(n + 1)]
# 양쪽에 연결하는 이유는?? 그럼 다른 문제들에서는 양쪽에 연결하면 안되나??
for _ in range(m):
a, b = map(int, input().split())
data[a].append(b)
data[b].append(a)
visited = [False for _ in range(n + 1)]
result = 0
def dfs(param_x, cnt):
global result
if param_x == y:
result = cnt
return
for i in data[param_x]:
if not visited[i]: # 만약 방문처리를 안하면 어떻게 될까?, 외워서 하지 말자. 하나하나에 다 이유가 있다.
visited[i] = True
dfs(i, cnt + 1)
visited[i] = False
dfs(x, 0)
if result == 0:
print(-1)
else:
print(result)
Q1. 왜 이 문제에는 DFS를 사용했을까?
어제 강의 질문 중에서 나는 이 문제를 BFS를 써야 한다고 답했다.
물론 틀린 말은 아니지만, DFS를 좀 더 깊게 자세히 이해했다면, BFS, DFS 둘 다 가능하겠네요 라고 답했을 것 같다.
DFS 간단 설명
DFS는 자신의 간선 중을 모두 탐색하는데, 한 간선에 대해 탐색할 때 그 간선과 연결된 모든 간선을 탐색한다.
이 과정에는 재귀의 의미가 내포되어 있다.
"한 간선에 대해 탐색할 때 그 간선과 연결된 모든 간선을 탐색한다." 이 부분은 각 간선 마다에 수행해줘야 하는 임무이다.
즉 한 간선만이 아니라, 각각의 간선에 대하여 재귀적으로 이 임무를 부여하는 것이다.
이 문제가 DFS에 적합한 이유는, 한 지점에 대하여 다른 하나의 지점까지 몇 depth를 갖는지를 구해야 하기 때문이다.
Q2. 왜 이 문제는 간선에 대한 정보를 부모와 자식 둘 다 가지고 있어야 할까?
엥,,? 나는 다른 그래프 문제를 풀 떄, 각자 자식의 간선만 가지고 있었는 줄 알았다..
근데 이전에 풀었던 문제를 다시보니, 서로 가지고 있었다,,?
왜지?? 자식만 가지고 있으면 안되나?? 어차피 백트래킹하게 되는데,,?
직접 해본 결과, 부모를 가지고 있지 않다면 백트래킹을 할 수 없다.
예를 들어, 1에서 10으로 갔다고 가정하자.
그럼 저기서 7로 다시 돌아가야 하는데, 돌아갈 방법이 없다.
그래서 인접 리스트 문제에서 자식과 부모 서로가 간선 정보를 가지고 있는 것 같다.
Q3. visited[i] = False부분을 빼줘도 똑같다. 어떤 차이가 있을까?
문제를 다시 한번 생각해보니, visited[i] = False부분을 뺴줘도 될 것 같았다.
이것이 있고 없고 차이가 어떤 차이가 있을까??
메모리도 똑같고 시간도 똑같이 나온다.
아,, 보통 visited[i] = False는 조합이나, 어떤 경우의 수, 브루트포스와 같은 문제에서 사용했다.
그때는 visited[i]를 체크 했을 때와 안했을 떄, 모두 다른 경우의 수로 구해줘야 했고,
for i in range(n)을 사용하여 그 모든 경우의 수를 구해줬다.
때문에 당시에는 visisted[i] = False처리가 필요했다.
왜냐하면 각 경우에 대해서 처음부터 돌기 때문에,, 그것이 유의미했다. (느낌은 알겠는데 말로 표현이 이게 맞나,,?)
근데 여기서 질문:
9
1 7
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
이거 했더니 4 나오는데 2여야 하는거 아닌가,,?