백준 - 1260 DFS와 BFS (파이썬)

첫 시도 : 上

문제를 파악하고 2차원 리스트형태로 만드는 것부터 막혔었다.

해답을 보고 했지만 이해하기가 어려웠다.

 

두번째 시도 : 中

해답을 보면 이제 어떤 식으로 짜여졌는지 이해가 간다.

 

 

DFS, BFS를 이용하는 문제

---

 

핵심

1. 입력값으로 노드의 간선을 입력하는데 2차원 배열형태로 갈 수 있는 곳을 1로 표시해서 만든다.

2. 방문한 노드는 다시 방문하지 않도록 visited를 선언한다.

3. 1번 노드부터 시작하기 때문에 리스트들을 만들 때 제일앞은 건너뛴다고 가정하고 노드의 개수 +1 로 리스트를 만든다.

 

연습을 위해 DFS와 BFS를 나눠서 코드를 써보자.

먼저 DFS.

n , m, s = map(int, input().split())

visited = [False] * (n+1)
graph = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

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


dfs(s)

여러번 연습해 본 결과 생각하면서 풀기에 성공했다.

dfs 문 내에서를 보자면 스타트노드를 파라미터로 받아서 visited 리스트에 True로 방문했다. 로 표시하고 

노드1번부터 방문했는지를 확인해서 방문을 안했고 2차원 리스트상에서 간선이 연결되어 있는 곳이라면

dfs(i)를 실행해서 깊숙히 나아간다.

 

 

다음 BFS

def bfs(s):
    queue = [s]
    while queue:
        v = queue[0]
        print(v)
        del queue[0]

        for i in range(1, n+1):
            if visited[i] == False and graph[s][i]:
                queue.append(i)
                visited[i] = True


n, m, s = map(int, input().split())

visited = [False] * (n+1)
graph = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1



bfs(s)
    

bfs는 큐 자료구조처럼 사용해서 먼저들어간 것이 먼저 나오도록(FIFO) 설계하는데 여기서는 하나씩 프린트로 출력해주기 위해서

일반적으로 그냥 queue라는 리스트를 선언하고 시작 노드를 넣고

 

while문을 이용해서 queue가 있을 때 동안은 계속 반복하게 만들고

queue안에 있는 것을 빼내거나(pop, popleft)

아니면 할당해서 특정 변수에 값을 넣고 프린트하고 삭제하고 ( 할당 후 del)

1번 노드부터 n번 노드까지 방문하기 위해서 for(1, n+1)을 하고

만약 아직 방문하지 않았고 2차원 리스트에서 방문 가능한 곳임을 확인했으면

1번부터 순차적으로 if문을 거쳐 해당 조건을 만족하는 것만 queue에 append한다.

다음 방문했다는 의미로 visited[i] = True를 한다.