[Python] BOJ 1260 : BFS와 DFS

https://www.acmicpc.net/problem/1260 <- click 이 될까?

 

요구사항 분석

BFS는 큐로 DFS는 스택으로 구현하라고 하던 데... 내 생각 과정을 보여주겠다.

N,M,V = map(int,input().split())

graph= [[],]

for i in range(M):
    graph.append(list(map(int,input().split())))

visited = [False] * (N+1)

def dfs(v):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

dfs(V)

• 의도를 먼저 설명해주겠다. 문장 앞의 번호는 코드가 있는 라인 순서다.

1. N, M, V 를 한 번에 입력 받기 위해 map 메서드를 사용했다. 
2. graph = [[], ] : 시작 노드를 1번 부터 시작하기 위해서 0 번째 를 비워둔다. 
3. 첫 번째 for문은 각 노드들의 연관 관계를 입력 받는다. 
4. 각 노드를 방문했는 지 확인하기 위해 불 값으로 초기화 해준다. N + 1 이유는 2번과 같은 이유이다. 
5. dfs 함수에 인자가 들어 왔을 때, 그 인자를 방문했다고 표시 해준다. 
6. 그리고 출력해준다. 

하지만 위 와 같이 한다면 아래와 같은 문제점을 야기한다. 

• 첫 번째 for문을 보면 각 노드들간의 연관성을 볼 수 없다. 단순히 한 쌍의 값으로 저장하고 있다. 
  • [[], [1, 2], [1, 3], [1, 4], [2, 4], [3, 4]]
• 따라서 두 번째 for 문은 의도한 대로 방문하지 않는다. 
• 어떻게 해결해야 될까? 
• 처음 입력을 받을 때, 각 노드의 연관성을 표시해주자. 

N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]

for i in range(M):
	u,v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

• 위 소스 코드를 작동 시켰을 때, 어떻게 작동되는 지 설명해보겠다.
• N, M, V = 4, 5, 1
• graph = [[], [], [], [], []] 
• for i in range(5): 5번 동안 반복
• 1 2 를 입력했다.
• graph[1] 에 2가 들어간다. graph = [[], [2], [],[],[]]
• graph[2]에 1이 들어간다. graph = [[],[2],[1],[],[]]
• 그렇게 5번 반복해서 각 노드들 간의 연관성을 보여주는 리스트로 바뀌었다. 

사용자로부터 입력을 받았을 때 들어가는 과정

N,M,V = map(int,input().split())

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

for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
print(graph)

# 예시로 1번 부터 4번 노드있다. 
visited = [False] * (N+1)

def dfs(v):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = ' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in (graph[v]):
        if not visited[i]:
            dfs(i)

dfs(V)

• 위 코드는 DFS 특성은 잘 보여준다. 하지만 아직도 문제를 풀기엔 문제가 있다.
• 그것은 사용자의 입력에 따라 각 배열이 정렬이 되지 않았다. 
• BOJ 에서는  번호가 낮은 순서대로 출력하게끔 되어 있다. 아래 사진을 보며 이해해보자. 

• 위 사진처럼 사용자의 입력에 따라 순서가 바뀐다. 하지만 이것은 DFS 방식은 맞다. 일반적으로 코테에서도 낮은 번호를 먼저 탐색하게 요구사항에 주기 때문에 정렬이 필요하다.
• dfs 함수안의 for 문을 

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

• sorted 해주면 된다. 

BFS  구현 

from collections import deque

def bfs(v):
    queue = deque([v])
    visited_bfs[v] = True

    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in sorted(graph[v]):
            if not visited_bfs[i]:
                queue.append(i)
                visited_bfs[i] = True

• 헷갈릴 수 있는 부분은… 모르겠다. 이해하기 쉽게 설명하겠다. 느낌적으로 우선 가져가길 바랍니다.
• 현재 시작 노드가 V로 사용자로 부터 입력을 받는다. 여기서는 1이다.
• bfs(1)
• queue = deque([1]) → queue 리스트가 만들어지고 안에 1이 들어감.
• visited_bfs[1] = True → 시작노드를 0이 아닌 1부터 시작하는 걸 생각하세요. 그리고 1번 노드를 방문했다고 표시 하는 겁니다.
• while queue → queue가 비어 있지 않을 때. 현재 queue = [1] 있죠.
• 1 = queue.popleft() → queue 맨 앞 인덱스를 제거합니다.
• print ~ : 방문했다고 가시적으로 보여줍니다.
• for i ~~~ : graph[1] = [2,3] 이 들어가 있다고 한다면…
• if ~ → visited_bfs[2] 과 [3]을 방문한적 있냐? 없죠?
• 그러면 queue에 2와 3을 넣습니다. queue = [2,3]
• 그 다음 2,3을 방문한 적 있다고 해줍니다.
• 반복합니다. 그러면 빼주기만 하다 queue 가 비게 되어 while 문이 종료됩니다.

답안 예시 소스 코드 

N,M,V = map(int,input().split())

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

for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
print(graph)

visited_dfs = [False] * (N+1)
visited_bfs = [False] * (N+1)

def dfs(v):
    visited_dfs[v] = True
    print(v, end = ' ')
    for i in sorted(graph[v]):
        if not visited_dfs[i]:
            dfs(i)
from collections import deque

def bfs(v):
    queue = deque([v])
    visited_bfs[v] = True

    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in sorted(graph[v]):
            if not visited_bfs[i]:
                queue.append(i)
                visited_bfs[i] = True

dfs(V)
print()
bfs(V)

 

 

+ 202409192125 복습

'''
# map 매서드를 사용해서 입력을 받는 이유는 
# 한 줄에 여러 개를 입력 받기 위해서 이다. 
# map (function, iterable) 기본 문법
# 자주 헷갈리는 것. map은 iterable 객체를 받기 때문에
# 정수형을 넣지 말자. 
# 또한, map 은 주소값을 반환하기 때문에 그냥 사용하면 주소값을 보여준다. 
# 따라서 그 값을 사용할 때는 괜찮지만 직접 출력할 지에는 list 등의 형태로
# 변환해주자. 
# n = list(map(int, input().split()))
# print(n)
'''
# N 노드의 개수, M 간선의 개수, V = 시작노드
N, M, V = map(int, input().split())

# 각 노드들의 연관성을 보여주는 입력을 M행개 받는다. 
# for _ in range(m):

# 각 노드들의 연관성을 보여주려면 먼저 리스트를 초기화해야 된다. (리스트컨프리헨션)
# N + 1 개 로 초기화 하는 이유는 문제에서 노드의 시작이 1이기 때문이다. 
graph = [[] for _ in range(N + 1)] 
'''
언더스코어를 사용하는 이유는 지금은 간지다... 인덱스 값이 필요없으니깐...
'''
# 이제 각 노드들의 연관성을 보여주는 입력을 M행개 넣을 수 있게 되었다. 
for _ in range(M):
    u,v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
print(graph)
'''
처음엔 단순히 u,v 의 입력만 받았었다. 
하지만 그렇게 받는다면 단순히 한 쌍의 입력을 저장하는 것 이상도 아니다. 
따라서 각 노드들의 연관성을 보여주고자. 위 같은 방식을 선택한 것이다. 
'''
# 해당 노드의 방문여부 확인, graph 초기화와 동일한 이유로 (N + 1)개로 초기화
visited_dfs = [False] * (N + 1)
visited_bfs = [False] * (N + 1)

# 준비는 끝났다. 위와 같이 주석을 단 이유는 코드 한 줄 한 줄 왜 필요한지 정리해보고 싶었기 때문이다.
def dfs(v):
    visited_dfs[v] = True
    print(v, end = ' ')

    for i in sorted(graph[v]):
        if not visited_dfs[i]:
            dfs(i)
from collections import deque
def bfs(v):
    queue = deque([v])

    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in sorted(graph[v]):
            if not visited_bfs(i):
                queue.append(i)
                visited_bfs(i) = True


dfs(V)
print()
bfs(V)

 위 소스코드가 익숙해지면 리팩토링할 부분 없나 살펴 보자. 아래 함수를 실행하고 print() 하는 부분이 마음에 안든다.