[백준] 11403번 경로 찾기 - (Python)

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

11403번: 경로 찾기

그래프 이론 중, 플로이드 - 워셜 방식으로 접근하는 문제입니다. 해당 경로까지 가는 방법이 1개라도 존재한다면, 1 그렇지 않다면 0을 출력하게 합니다. 본인은 단순히 BFS로만 접근했었고, 메모리초과로 인해 조금 더 단순하게 코드를 변형한 뒤, 구현했습니다. 

그러나 플로이드 - 워셜 방식을 알고 난 뒤, 문제의 접근이 굉장히 쉬워졌습니다. 그래서 BFS, 플로이드 - 워셜 방식 2가지에 대해서 알아보려 합니다.

 

※ 고려사항

1. 입출력 행렬

2. 구현 방식

3. 출력 방식

---

1. 입출력 행렬

노드의 개수 N을 입력 받으면 3 x 3 행렬로 입출력 행렬을 만들게 됩니다. 사실 BFS 나 DFS 문제를 풀 때, 굉장히 많이 받아오는 형식이기 때문에 구체적인 설명은 생략하도록 하겠습니다. 설명이 필요하신 분은 https://yunway.tistory.com/3 해당 설명을 참고해주세요!

리스트 컴프리헨션으로 다음과 같이 코드를 구현합니다. 또 출력 행렬은 해당 위치에서 연결이 가능하면 1 처리를 하기 위해 0으로 값을 초기화합니다.

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

# 그래프 생성
graph = [list(map(int, input().split())) for _ in range(n)]

# 출력할 행렬 생성
matrix = [[0] * n for _ in range(n)]

 

2. 구현 방식

사실 이 문제에서 핵심이 되는 부분입니다. 처음에 일반적인 BFS로 구현을 하여 81% 채점과정에서 메모리초과가 발생했습니다.

실패한 BFS

init_graph = graph

def bfs(start, end):
    global graph
    global init_graph
    global visit

    queue = deque([start])
    visit[start] = 1
    while queue:
        v = queue.popleft()

        for w in graph[v]:
            if w == end:
                visit = [0] * n
                return 1

            if visit[w] == 0:
                queue.append(w)
    
    graph = init_graph
    visit = [0] * n
    return 0

따라서 조금 더 효율적인 방식이 필요했고, 플로이드 워셜 알고리즘을 알게 되었습니다. 

해당 알고리즘은 모든 정점 간의 최단 경로를 알려는 알고리즘입니다. 따라서 해당 문제에서 방문처리를 하기 위해 핵심적으로 사용되는 알고리즘입니다.

그래서 BFS에 이를 적용하여 각 노드의 방문 list를 생성하여, 방문하지 않았으면서, 해당노드로 연결되는 간선이 존재한다면 해당 좌표는 1로 처리합니다.

코드는 다음과 같습니다.

 

BFS

# BFS 
def bfs(start):
    
    # 시작노드를 Queue에 삽입
    queue = deque([start])

    # 방문처리 배열
    visit = [0 for _ in range(n)]

    while queue:
        v = queue.popleft()

        # 방문되지 않았으면서, 1이면 방문처리 후, 해당 노드 queue 삽입
        for i in range(n):
            if visit[i] == 0 and graph[v][i] == 1:
                queue.append(i)
                visit[i] = 1
                matrix[start][i] = 1

 

해당 문제를 플로이드 - 워셜 알고리즘을 통해 풀어봅니다. 해당 방법은 3중 for문으로 구성되는데, 2개의 for문은 해당 행렬에 접근하는 구문이고, 남은 for문은 해당 간선을 거쳐서 갈 수 있는지 유무를 판단해 주는 구문입니다. 따라서 굉장히 간단하게 코드를 구현할 수 있습니다. 주석으로 설명을 해두었으니, 참고 바랍니다.

 

플로이드 - 워셜

for k in range(n):
    for i in range(n):
        for j in range(n):

            # i -> k -> j K를 거쳐 도달 가능하면 1
            if graph[i][k] and graph[k][j]:
                graph[i][j] = 1

 

3. 출력 방식

bfs는 시작 노드만 보내주면, 해당 노드와 모든 노드와의 도달 유무를 판단하기 때문에 n번 반복하면 된다.

출력의 경우 각 행렬의 행을 출력하면 되기 때문에 다음과 같이 구현할 수 있다.

for i in range(n):
    bfs(i)

# 출력
for i in matrix:
    print(*i)

---

전체코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

# 그래프 생성
graph = [list(map(int, input().split())) for _ in range(n)]

# 출력할 행렬 생성
matrix = [[0] * n for _ in range(n)]

# BFS 
def bfs(start):
    
    # 시작노드를 Queue에 삽입
    queue = deque([start])

    # 방문처리 배열
    visit = [0 for _ in range(n)]

    while queue:
        v = queue.popleft()

        # 방문되지 않았으면서, 1이면 방문처리 후, 해당 노드 queue 삽입
        for i in range(n):
            if visit[i] == 0 and graph[v][i] == 1:
                queue.append(i)
                visit[i] = 1
                matrix[start][i] = 1

for i in range(n):
    bfs(i)

# 출력
for i in matrix:
    print(*i)

# 플로이드 - 워셜 방식
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):

            # i -> k -> j K를 거쳐 도달 가능하면 1
            if graph[i][k] and graph[k][j]:
                graph[i][j] = 1

for g in graph:
    print(*g)

---

해당 문제를 통해 그래프 문제는 정말 다양한 알고리즘이 존재함을 알게 되었습니다. DFS, BFS를 이제 체화했다고 생각했는데, 아직 해야 할 것이 참 많다고 느꼈습니다.. 그 덕분에 더 노력해야 함을 느끼는 문제였습니다.

설명의 오류나, 궁금하신 점은 언제든 피드백해주시면 감사하겠습니다 ^~^