[알고리즘 설명][Python] 그래프 탐색(graph search)

이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.

혹시나 모르는 부분이 있으면 댓글로 질문해주세요.

 

한 줄 요약 : 그래프 탐색은 말 그대로 그래프 탐색입니다. 그래프 안에 있는 정보들을 잘 탐색하면 됩니다. 그리고 방문 여부 리스트를 꼭 추가해주세요.

 

그래프 탐색은 무엇일까요?

기존 그래프 이론에서 방문 여부 기능을 추가해서 그래프 안에 있는 정보들을 탐색하는 것입니다.

설마 여기서 bfs와 dfs 나와서 이 게시글이 어려울 것 같다고 생각했나요?

아니요, 여기 게시글에는 bfs와 dfs는 나중에 따로 설명하고 여기서는 방문 여부 체크만 확인할 것입니다.

 

그러므로 복잡한 그래프 탐색 방법은 다음에 bfs, dfs 설명하는 과정에서 알려주기로 하고 여기서는 선형 그래프만 설명하도록 하겠습니다.

N = 3 # 노드 개수

# 인접 리스트 선언
graph:list = [[] for _ in range(N + 1)]

# edge 정보 추가
graph[1].append((2, 3))
graph[2].append((3, 5))

이런 그래프가 있다고 가정합니다.

저는 1번 노드부터 시작하여 3번 노드까지 방문하면서 모든 간선들의 합을 구하고 싶어요.

여기에 방문 여부 체크를 확인하겠습니다.

N = 3

visited:list = [False] * (N + 1)

여기서 visited는 방문 여부 체크해주는 리스트이며 아직 방문하지 않았으므로 False로 해줍니다.

자, 우선 1번 노드를 방문해줍니다.

그러면 visited[1] = True로 바꿔주면 됩니다.

# 0번 노드는 어차피 방문할 계획이 없으므로 이미 방문했다고 처리해서 중복 탐색을 방지합니다.
visited[0] = True

# 1번 노드를 방문했으니 True 처리합니다.
visited[1] = True

이제 1번 노드에서 2번 노드로 이동할 것입니다.

이것을 코드로 표현하면 다음과 같습니다.

sum_of_edge_value:int = 0
current_node:int = 1
# 만약 아직 2번 노드를 방문하지 않았다면
if not visited[2] :
    sum_of_edge_value += graph[current_node][0][1]
    print(sum_of_edge_value)
    current_node = graph[current_node][0][0]
    print(current_node)

graph[1] = [(2, 3)]이므로 graph[1][0] = (2, 3)이며 여기서 간선의 값을 탐색해야 하니 graph[1][0][1]으로 해줍니다.

그러면 간선들의 합에 3이 추가되어 첫번째 print()에서 3이 나옵니다.

그리고 최근 노드(current_node)는 graph[1][0][0] 값이 대입되니 최근 노드는 2번 노드로 갱신됩니다.

 

지금부터 제가 직접 1번 노드부터 3번 노드까지 모두 다 탐색해서 간선들의 값을 모두 더하도록 하겠습니다.

N = 3 # 노드 개수

# 인접 리스트 선언
graph:list = [[] for _ in range(N + 1)]

# edge 정보 추가
graph[1].append((2, 3))
graph[2].append((3, 5))

N = 3

visited:list = [False] * (N + 1)

# 0번 노드는 어차피 방문할 계획이 없으므로 이미 방문했다고 처리해서 중복 탐색을 방지합니다.
visited[0] = True

# 1번 노드를 방문했으니 True 처리합니다.
visited[1] = True

result:int = 0 # 간선들의 합
current_node:int = 1 # 최근 방문한 노드는 1번 노드입니다.

# 해당 노드에 방문해야 하는 노드가 있는지 확인합니다.
while graph[current_node] :
    # 다음에 가야 하는 노드 정보를 저장합니다.
    next_node:int = graph[current_node][0][0]
    # 만약 아직 방문하지 않았다면
    if not visited[next_node] :
        # 해당 간선의 값을 추출하고 더합니다.
        value:int = graph[current_node][0][1]
        result += value
        # 최근 방문 노드를 갱신합니다.
        current_node = graph[current_node][0][0]

print(result)

뭔가 복잡해 보이지만 주석대로 천천히 따라가면 금방 이해할 수 있을 것입니다.

이것을 실행하면 결과는 8이 나옵니다.

간선들의 value 합과 일치합니다.

 

 

 

이제부터 실전성을 기르기 위해 지금부터 당신은 호텔 직원이 되는 것입니다.

1101호부터 1112호까지 확인해서 청소를 해야 합니다.

교대하기 전에 1103호는 현재 인테리어 공사 중이라서 방 안에 들어갈 수 없으며 1108호와 1109호는 이미 이전 직원이 청소를 마친 상태입니다.

이 때 최대 일의 양이 100이라고 가정할 때 11층에 총 얼마만큼 일을 해야 하는 것일까요?

 

우선 그래프 선언을 하겠습니다.

F = 15 # 이 호텔은 총 15층입니다.
R = 12 # 그리고 각 층마다 총 12개의 room이 있습니다.

# 인접 리스트로 선언합니다.
# 이 때 graph[현재 층수][현재 방 호수][0] = 청소해야 하는 양으로 정합니다.
graph:list = [[[0] for _ in range(R + 1)] for _ in range(F + 1)]

그리고 간선들의 정보와 방의 정보를 저장하도록 합니다.

편의상 단방향 그래프라고 가정합니다.

# 그래프 정보를 저장합니다.
graph[11][1].append((11, 2))
graph[11][2].append((11, 3))
graph[11][3].append((11, 4))
graph[11][4].append((11, 5))
graph[11][5].append((11, 6))
graph[11][6].append((11, 7))
graph[11][7].append((11, 8))
graph[11][8].append((11, 9))
graph[11][9].append((11, 10))
graph[11][10].append((11, 11))
graph[11][11].append((11, 12))

# 11층에 있는 모든 방의 일의 양을 저장합니다.
graph[11][1][0] = 34
graph[11][2][0] = 9
graph[11][3][0] = 100
graph[11][4][0] = 56
graph[11][5][0] = 37
graph[11][6][0] = 82
graph[11][7][0] = 62
graph[11][8][0] = 5
graph[11][9][0] = 10
graph[11][10][0] = 64
graph[11][11][0] = 43
graph[11][12][0] = 91

그 다음 방문 체크 리스트를 만들어 옵니다.

그리고 사전에 이미 방 청소가 끝나거나 공사 중이라서 못 간 곳은 "이미 방문했다"고 처리해줍니다.

# 11층 방문 체크리스트를 만듭니다.
visited:list = [False for _ in range(R + 1)]

# 이전 직원이 이미 청소하거나 공사 중인 방은 이미 방문 처리해서 그 방들은 확인하지 않도록 합니다.
visited[0] = True
visited[3] = True
visited[8] = True
visited[9] = True

그 다음부터는 아래에 나머지 소스 코드들을 구현해서 당신이 해야 하는 총 일의 양을 구합니다.

total_work = 0
curr_room = 1 # 1101호부터 탐색 시작

print("11층 청소(탐색) 시작\n")

while True :
    # 1. 현재 방의 상태 확인 및 청소 (방문하지 않은 방일 경우)
    if not visited[curr_room] :
        work = graph[11][curr_room][0] # 0번 인덱스 : 일의 양
        total_work += work
        visited[curr_room] = True      # 청소 완료 후 방문 처리
        print(f"11{curr_room:02d}호 청소 완료! (일의 양 : {work})")
    else :
        print(f"11{curr_room:02d}호는 공사 중이거나 이미 청소됨. 패스합니다.")

    # 2. 다음 방으로 이동할 수 있는 간선(복도)이 있는지 확인
    # 우리가 설계한 장부는 리스트 길이가 1보다 크면 뒤에 간선 정보가 들어있습니다.
    if len(graph[11][curr_room]) > 1 :
        next_floor, next_room = graph[11][curr_room][1] # 1번 인덱스 : 연결된 다음 방
        curr_room = next_room # 다음 방으로 이동
    else :
        # 더 이상 뒤에 연결된 방(간선)이 없으면 탐색 종료
        print("\n복도 끝에 도달했습니다. 탐색 종료.")
        break

print(f"\n오늘 11층에서 수행한 총 일의 양 : {total_work}\n")
print("오늘 11층만 청소하고 나머지는 호텔 프론트 데스크에서 근무하다가 교대하면 된다고 합니다.")
print("오늘도 수고 많으셨습니다!")

 

이렇게 해서 호텔 직원인 당신은 지금부터 열심히 일을 합니다.

일부 방들은 공사 중이거나 이미 청소 끝냈다고 했으니 1103호, 1108호, 1109호는 무시하고 나머지 방들을 찾아서 직접 청소합니다.

이 때 실시간으로 그 방에 얼마나 청소했는지 표시됩니다.

그리고 오늘 청소를 얼마나 했는지 표시되며 오늘은 11층만 청소하면 된다고 합니다.

그 뒤 프론트 데스크에서 고객님들을 안내해주다가 교대하면 됩니다!

 

아래는 전체 소스 코드입니다.

F = 15 # 이 호텔은 총 15층입니다.
R = 12  # 그리고 각 층마다 총 12개의 room이 있습니다.

# 인접 리스트로 선언합니다.
# 이 때 graph[현재 층수][현재 방 호수][0] = 청소해야 하는 양으로 정합니다.
graph:list = [[[0] for _ in range(R + 1)] for _ in range(F + 1)]

# 그래프 정보를 저장합니다.
graph[11][1].append((11, 2))
graph[11][2].append((11, 3))
graph[11][3].append((11, 4))
graph[11][4].append((11, 5))
graph[11][5].append((11, 6))
graph[11][6].append((11, 7))
graph[11][7].append((11, 8))
graph[11][8].append((11, 9))
graph[11][9].append((11, 10))
graph[11][10].append((11, 11))
graph[11][11].append((11, 12))

# 11층에 있는 모든 방의 일의 양을 저장합니다.
graph[11][1][0] = 34
graph[11][2][0] = 9
graph[11][3][0] = 100
graph[11][4][0] = 56
graph[11][5][0] = 37
graph[11][6][0] = 82
graph[11][7][0] = 62
graph[11][8][0] = 5
graph[11][9][0] = 10
graph[11][10][0] = 64
graph[11][11][0] = 43
graph[11][12][0] = 91

# 11층 방문 체크리스트를 만듭니다.
visited:list = [False for _ in range(R + 1)]

# 이전 직원이 이미 청소하거나 공사 중인 방은 이미 방문 처리해서 그 방들은 확인하지 않도록 합니다.
visited[0] = True
visited[3] = True
visited[8] = True
visited[9] = True

total_work = 0
curr_room = 1 # 1101호부터 탐색 시작

print("11층 청소(탐색) 시작\n")

while True :
    # 1. 현재 방의 상태 확인 및 청소 (방문하지 않은 방일 경우)
    if not visited[curr_room] :
        work = graph[11][curr_room][0] # 0번 인덱스 : 일의 양
        total_work += work
        visited[curr_room] = True      # 청소 완료 후 방문 처리
        print(f"11{curr_room:02d}호 청소 완료! (일의 양 : {work})")
    else :
        print(f"11{curr_room:02d}호는 공사 중이거나 이미 청소됨. 패스합니다.")

    # 2. 다음 방으로 이동할 수 있는 간선(복도)이 있는지 확인
    # 우리가 설계한 장부는 리스트 길이가 1보다 크면 뒤에 간선 정보가 들어있습니다.
    if len(graph[11][curr_room]) > 1 :
        next_floor, next_room = graph[11][curr_room][1] # 1번 인덱스 : 연결된 다음 방
        curr_room = next_room # 다음 방으로 이동
    else :
        # 더 이상 뒤에 연결된 방(간선)이 없으면 탐색 종료
        print("\n복도 끝에 도달했습니다. 탐색 종료.")
        break

print(f"\n오늘 11층에서 수행한 총 일의 양 : {total_work}\n")
print("오늘 11층만 청소하고 나머지는 호텔 프론트 데스크에서 근무하다가 교대하면 된다고 합니다.")
print("오늘도 수고 많으셨습니다!")

[결과]

11층 청소(탐색) 시작

1101호 청소 완료! (일의 양 : 34)
1102호 청소 완료! (일의 양 : 9)
1103호는 공사 중이거나 이미 청소됨. 패스합니다.
1104호 청소 완료! (일의 양 : 56)
1105호 청소 완료! (일의 양 : 37)
1106호 청소 완료! (일의 양 : 82)
1107호 청소 완료! (일의 양 : 62)
1108호는 공사 중이거나 이미 청소됨. 패스합니다.
1109호는 공사 중이거나 이미 청소됨. 패스합니다.
1110호 청소 완료! (일의 양 : 64)
1111호 청소 완료! (일의 양 : 43)
1112호 청소 완료! (일의 양 : 91)

복도 끝에 도달했습니다. 탐색 종료.

오늘 11층에서 수행한 총 일의 양 : 478

오늘 11층만 청소하고 나머지는 호텔 프론트 데스크에서 근무하다가 교대하면 된다고 합니다.
오늘도 수고 많으셨습니다!

 

오늘 그래프 탐색을 아주 간단하게 알아보고 이 그래프 탐색이 어떻게 활용하는지 실전 사례까지 들고 왔습니다.

그리고 이 프로그램은 좀만 수정하면 좀 더 유연하게 만들 수 있습니다.

예시로 청소해야 하는 양에서 쓰레기 양, 배치해야 하는 양 등 다양한 일들이 존재하거나 혹은 중간에 엘리베이터가 있어서 1105호 <-> 1205호도 가능하거나 혹은 11층 뿐만 아니라 10층도 해야 하는 경우 그래프 없이 구현하기 정말로 어렵습니다.

한 번 직접 수정해보세요! 그러면 호텔 직원의 업무가 좀 더 수월해질 것입니다.

 

오늘도 수고 많으셨습니다!