[Python] 백준 12849: 본대 산책 (3가지 풀이 비교)

문제 링크

12489번: 본대 산책

문제 요약

학교 지도가 그래프로 주어진다. 정보과학관에서 출발해 산책한 후 D분 후, 정보과학관으로 돌아오는 산책 경로의 수를 구한다. 단, 산책을 하며 건물에 머무르는 경우는 없고, 각 건물 간 이동 시간은 1분이다. 

풀이 설명

백준에 나와있는 이 문제의 알고리즘 유형은 DP와 그래프 이론이었다.

처음 문제를 받고 15분 정도 하다가 감을 잘 못 잡는 것 같아서 알고리즘 유형을 봤다.

내가 이해하고 있는 DP는 이전의 계산값을 사용하여 다음 계산값을 구하는 것, 그래프 이론은 그래프 사용하는 것(?) 학교의 '그래프 이론' 수업을 들어야겠다는 생각이 든다...😅

 

지금 글 쓰면서 찾은 건데, 파이썬 그래프 구현 방법이 내가 한 방법과 같다..!!

 

나의 풀이

def possibilities(states, school):
    result_states={'학생회관': 0,
            '진리관': 0,
            '형남공학관': 0,
            '한경직기념관': 0,
            '신양관': 0,
            '미래관': 0,
            '전산관': 0,
            '정보과학관': 0}
    
    for state, people in states.items():
        for route in school[state]:
            result_states[route]+=people
    
    for state, people in result_states.items():
        result_states[state]=people%1000000007
    return result_states
    
school={'학생회관': ['진리관', '형남공학관'],
         '진리관': ['학생회관', '한경직기념관', '신양관'],
         '형남공학관': ['학생회관', '한경직기념관'],
         '한경직기념관': ['형남공학관', '진리관', '신양관', '미래관'], 
         '신양관': ['진리관', '한경직기념관', '미래관', '전산관'],
         '미래관': ['한경직기념관', '신양관', '전산관', '정보과학관'], 
         '전산관': ['신양관', '미래관', '정보과학관'],
         '정보과학관': ['전산관', '미래관']}

states={'학생회관': 0,
            '진리관': 0,
            '형남공학관': 0,
            '한경직기념관': 0,
            '신양관': 0,
            '미래관': 0,
            '전산관': 0,
            '정보과학관': 1}

D=int(input())
for walk in range(D):
    states=possibilities(states, school)
print(states["정보과학관"])

 

나의 풀이 스타일은 최대한 이해한 바를 정리하여 그대로 구현하는 것이라고 생각한다. 아직 코딩 테스트에 익숙하지 않아서 그런지도 모르겠지만, 조금 비효율지언정 문제를 푸는 확률을 더 높이려고 한다.

메모리를 엄청 쓰긴 했다;;

 

제출 현황을 봤을 때, 다른 사람들의 메모리 사용량이 확연히 적어서 제 코드가 비효율적이라는 것이 느껴졌다. 기본적으로 C와 Python의 차이이기도 했으나, 같은 Python 내에서도 풀이 방법+메모리와 시간 사용량이 확연히 차이나서 비교해보고자 한다.

 

다른 사람 풀이1

밸런스 있는 메모리&시간 사용량인 것 같다.

'''
0: 정보과학관
1: 전산관
2: 미래관
3: 신양관
4: 환경직
5: 진리관
6: 학생회관
7: 형남공학관
'''

DP = [1,0,0,0,0,0,0,0] #0분일떄

def nxt(state):
    tmp = [0 for _ in range(8)]
    tmp[0] = state[1] + state[2] # 정보과학관에 오려면 전산, 미래관에서 1분전에 오기
    tmp[1] = state[0] + state[2] + state[3]
    tmp[2] = state[0] + state[1] + state[3] + state[4]
    tmp[3] = state[1] + state[2] + state[4] + state[5]
    tmp[4] = state[2] + state[3] + state[5] + state[7]
    tmp[5] = state[3] + state[4] + state[6]
    tmp[6] = state[5] + state[7]
    tmp[7] = state[4] + state[6]
    return(tmp)
for i in range(int(input())):
    DP = nxt(DP)
print(DP[0] % 1000000007)

 

또 글 쓰면서 깨달았는데 1차원 DP, 2차원 DP가 무엇인지이다.

이 분은 1차원 DP, 즉 1차원 list로 DP를 구현하여 문제를 해결했다.

배울 점은 각 대학동마다 index를 정의하고 0, 1의 간결한 리스트로 표현하였다는 점이다.

좋다 👍

 

다른 사람 풀이2

C로 푸신 분들이 대부분 이 풀이를 사용한 것 같은데, 지금도 이 풀이가 잘 이해가 되지 않는다... 🥲

C로 같은 방식의 풀이는 메모리&시간 사용량이 훨씬훨씬 적다.

# https://www.acmicpc.net/problem/12849
D = int(input())
matrix = [
    [0, 1, 1, 0, 0, 0, 0, 0],
    [1, 0, 1, 1, 0, 0, 0, 0],
    [1, 1, 0, 1, 1, 0, 0, 0],
    [0, 1, 1, 0, 1, 1, 0, 0],
    [0, 0, 1, 1, 0, 1, 0, 1],
    [0, 0, 0, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0, 1, 0]
]
l = len(matrix)
# 행렬의 곱셉
mod = 1000000007
def matrix_dot(mat1, mat2):
    row, k = len(mat1), len(mat1[0])
    k, col = len(mat2), len(mat2[0])
    result = [[0 for _ in range(col)] for _ in range(row)]
    
    for i in range(row):
        for j in range(col):
            for k_ in range(k):
                result[i][j] += (mat1[i][k_] * mat2[k_][j])%mod
            result[i][j] %= mod
    return result

# 단위행렬
ret = [[0 for _ in range(l)] for _ in range(l)]
for i in range(l):
    for j in range(l):
        if i == j:
            ret[i][j] = 1
            
# 행렬의 거듭제곱 & 분할정복(비트연산)
while D:
    if D & 1 == 1:
        ret = matrix_dot(ret, matrix)
    D >>= 1
    matrix = matrix_dot(matrix, matrix)
    
print(ret[0][0])

코드를 직관적으로 해석해보면,

ret=단위행렬

matrix=학교 건물 간 관계를 행렬로 나타낸 것

D가 홀수일 때, ret를 업데이트하고 while문으로 D가 0이 될 때까지 2로 나눈다. 각 순환마다 matrix는 자기 자신과 행렬곱이 된다.

 

이 문제를 누군가 설명해주면 좋겠다...😅

곰곰히 생각해도 왜 행렬의 거듭제곱이 가능한 경로 갯수와 연관되는지 잘 모르겠당...