[백준 1260번] BFS, DFS

 

 

[백준 1260번] DFS와 BFS]

 

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

1260번: DFS와 BFS

 

 

(정답)

처음 해보는 문제라서 많이 어려워서 다른 답들을 참고했다.

n,m,v=map(int,input().split())
mat=[[0]*(n+1) for _ in range(n+1)]
visit=[0]*(n+1)

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

def dfs(start):
    visit[start]=1
    print(start, end=' ')
    for i in range(1,n+1):
        if visit[i]==0 and mat[start][i]==1:
            dfs(i)

def bfs(start):
    queue=[start]
    visit[start]=1

    while queue:
        start=queue.pop(0)
        print(start, end=' ')
        for i in range(1,n+1):
            if visit[i]==0 and mat[start][i]==1:
                queue.append(i)
                visit[i]=1

dfs(v)
print()
visit=[0]*(n+1)
bfs(v)

 

 

코드만 보면 복잡해보인다.

DFS 부터 살펴보면서 궁금했던 점들을 정리해보자.

 

(DFS 코드)

n,m,v=map(int,input().split())
mat=[[0]*(n+1) for _ in range(n+1)]
visit=[0]*(n+1)

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

def dfs(start):
    visit[start]=1
    print(start, end=' ')
    for i in range(1,n+1):
        if visit[i]==0 and mat[start][i]==1:
            dfs(i)

dfs(v)

 

(n+1) X (n+1) 행렬은 왜 만들까?

코드의 행렬 구조 부터 살펴보자.

 

 

📍코드에서 사용하는 행렬 원리

 

→ mat=[[0]*(n+1) for _ in range(n+1)]

 

 

→ for i in range(n+1):

          x,y=map(int, input().split())

          mat[x][y]=mat[y][x]=1

 

 

 

 

📍그래프에서 (1,2)와 (2,1)은 같다. 그래서 아래와 같은 대칭 행렬이 나오는 것이다.

   아래 행렬이 우리가 DFS에서 사용하는 것이다.

 

 

→ 빨간색 1~4는 그래프 정점의 번호이면서 인덱스 번호와 같다.

→ (1,2)이 연결되었다면 mat[1][2] = mat[2][1] = 1 이 된다.

 

 

 

 

 

📍간혹 n X n 행렬로 만들면 안되는지 궁금할 수 있는데, 만약 그렇게 되면

→ (1,2)이 연결되었을 때 mat[0][1] = mat[1][0] = 1 이 된다.

   우리는 위와 같이 (n+1) X (n+1) 행렬을 사용할 때 더 편리함을 알 수 있다.

 

 

---

 

(BFS 코드)

n,m,v=map(int,input().split())
mat=[[0]*(n+1) for _ in range(n+1)]
visit=[0]*(n+1)

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

def bfs(start):
    queue=[start]
    visit[start]=1

    while queue:
        start=queue.pop(0)
        print(start, end=' ')
        for i in range(1,n+1):
            if visit[i]==0 and mat[start][i]==1:
                queue.append(i)
                visit[i]=1

bfs(v)

 

📍whlie queue: 의 의미

→ queue 이름의 리스트에 원소가 없으면 반복을 중단한다.

   즉, 이어지는 정점이 없으면 멈추게 된다.

 

 

 

📍queue 리스트를 사용하는 이유

예제 입력2) (1,2) (3,1), (3,4) (5,2), (5,4)

start=3, queue=[1,4]  *queue.pop(0): 리스트의 가장 첫번째 요소를 선택해서 제거한다.

start=1, queue=[4,2]  *큐 자료구조의 FIFO: 가장 먼저 입력된 데이터가 먼저 삭제된다.

start=4, queue=[2,5]

start=2, queue=[5]

start=5, queue=[]  *queue에 원소가 없으므로 while문 종료

 

 

 

 

📍리스트.pop(i)

→ 리스트의 해당 인덱스 요소를 제거한다.

→ i가 없으면 마지막 요소를 제거한다. ex) 리스트.pop()

 

 

 

 

 

 

한 문제 만으로 BFS, DFS를 이해하지 못하는 것은 당연한 일이다.

다른 문제들을 풀면서 조금씩 이해해나가도록 하자.