[알고리즘] 백준 1260 파이썬

백준 1260 풀이(파이썬)

전체코드는 더보기를 눌러주세요.

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

# 정점이 n개일 때, n*n크기의 이차원 배열을 생성한다.

a = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(m):

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

# x와y가 연결되어있음을 의미함. 방향은 무의미하므로 반대도 성립

a[x][y] = a[y][x] = 1




def dfs(start_node, visited_node):

# 모든 노드를 돌아다니면서 한 노드 다 팔 때 까지

# stack에 시작노드를 입력하고

# visited node에 시작노드를 입력하면서 pop

# visited하지않은 노드 다 방문

stack = [start_node]

while stack:

current_node = stack.pop()

visited_node.append(current_node)

for i in range(len(a[start_node])):

if a[start_node][i] == 1 and (i not in visited_node):

dfs(i, visited_node)

return visited_node




def bfs(start_node, visited_node):

visited_node = []

queue = [start_node] # startnode에서 시작한다

while queue:

current_node = queue.pop(0)

visited_node.append(current_node)

# 그래프 내의 start node열의 개수만큼(연결가능한?) for문,

for i in range(len(a[start_node])):

# 현재노드와 인접한 노드가 연결되어있고, i값을 방문하지않았다면

# 큐에 없을때 라는 조건이 추가 된 이유: 방문하지않은 노드가 또 ㅊ

if a[current_node][i] == 1 and (i not in visited_node) and (i not in queue):

queue.append(i)

return visited_node




print(" ".join(map(str, (dfs(v, [])))))

print((" ".join(map(str, bfs(v, [])))))

DFS 와 BFS의 개념을 적용하여 푸는 문제였다.

이 문제에선

 

# 입력된 정점의 개수(n)를 이용해 또다른 input값인 x,y를 전처리하는것

# 전처리 된 값을 이용해 DFS와 BFS를 이용해 모든 정점을 방문하는것

# 방문한 정점을 list형태가 아닌 string형태로 출력하는것

 

이 필요하다.

 

우선 DFS와 BFS를 문제에 제시된 예시를 이용해 나타내면 아래와 같다.

예시2 를 BFS로 표현함

예시2를 DFS로 표현함

# 전처리

이렇게 연결되어있다는 사실을 코드로 표현해서 전달할 필요가 있다.

여러가지 방법이 있을테지만, 나는 아래와 같이 이중배열을 이용해 표현했다.

 

 

n*n 이중배열을 만들면 위의 그림같이 마치 행렬처럼 표현할 수 있다.

연결되어있지않은 좌표는 0으로 표시하고, 연결되어있는 좌표는 1로 표시한다.

이 때, a[1][2] 도 연결되어있고, a[2][1]도 연결되어있다.(연결에 방향성이 없다)

해당 내용을 코드로 표현하면

 

n, m, v = map(int, input().split())
# 정점이 n개일 때, n*n크기의 이차원 배열을 생성한다.
a = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    # x와y가 연결되어있음을 의미함. 방향은 무의미하므로 반대도 성립
    a[x][y] = a[y][x] = 1

# BFS : 같은라인의 노드를 다 보고 하위라인으로 이동

start_node (v)에서 시작해서, start_node에 연결된 노드를 전부 확인 후 하위 노드로 내려간다. 

예시2에서 입력값 5,5,3 을 입력했다면,

a[3][i]부터 시작하여 해당 행에 연결된 값이 있는지 확인한다.

 

def bfs(start_node, visited_node):
    visited_node = []
    queue = [start_node]  # startnode에서 시작한다
    while queue:
        current_node = queue.pop(0)
        visited_node.append(current_node)
        # 그래프 내의 start node열의 개수만큼(연결가능한?) for문,
        for i in range(len(a[start_node])):
            # 현재노드와 인접한 노드가 연결되어있고, i값을 방문하지않았다면
            # 큐에 없을때 라는 조건이 추가 된 이유: 방문하지않은 마지막 노드가 또 추가되기 때문
            if a[current_node][i] == 1 and (i not in visited_node) and (i not in queue):
                queue.append(i)
    return visited_node

# DFS : 한 노드를  모두 탐색 후 다음 노드로 이동

start_node(v)에서 시작해서, start_node의 하위 노드로 이동한다. 

start_node의 하위노드에서 또다시 하위노드로 이동하거나

이동할 하위노드가 없을 경우 상위노드의 인접 노드로 이동한다.

 

def dfs(start_node, visited_node):
    # 모든 노드를 돌아다니면서 한 노드 다 팔 때 까지
    # stack에 시작노드를 입력하고
    # visited node에 시작노드를 입력하면서 pop
    # visited하지않은 노드 다 방문
    stack = [start_node]
    while stack:
        current_node = stack.pop()
        visited_node.append(current_node)
        for i in range(len(a[start_node])):
            if a[start_node][i] == 1 and (i not in visited_node):
                dfs(i, visited_node)
    return visited_node

# list를 string으로 받기

join과 map을 활용하여 원하는 형태로 바꿔준다.

print(" ".join(map(str, (dfs(v, [])))))
print((" ".join(map(str, bfs(v, [])))))