백준 12849: 본대 산책 (Python)

문제

숭실 대학교 정보 과학관은  캠퍼스의 길 건너편으로 유배를 당했다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 본대를 가고 싶어 한다. 어느 날 준영이는 본대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.

(편의 상 문제에서는 위 건물만 등장한다고 가정하자)

한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.

해설

다이나믹 프로그래밍(DP), 그리고 약간의 그래프 이론이 가미된 문제다. 처음 봤을 때에는 어떻게 풀어야 하나 싶었던 문제 중 하나인데, DP 문제 풀이의 핵심인 '작은 부분부터 생각하기' 를 해본다면 아이디어를 떠올리기 수월하다.

숭실대학교 건물 지도

'산책을 시작 한 지 D분 일 때, 정보과학관에 도착할 수 있는 모든 경우의 수' 가 문제에서 요구하는 내용이다.

따라서, i분 째에 각 건물마다 도착할 수 있는 경우의 수를 DP 셋에 저장해둔다면 다음과 같은 결과를 얻을 수 있다.

각 건물의 인덱스는 임의로 붙여주었다

테이블이 만들어지는 원리는 다음과 같다.

i분 째에 건물 A에 도착하는 경우의 수
= (i-1)분 째에 건물 A와 이어진 건물들에 도착하는 경우의 수의 합

위 원리만 봐서는 이해가 잘 되지 않을 수 있으므로, 어떻게 위와 같은 표가 만들어졌는지 사고의 흐름을 보자.

 

1. 0분

0분 째에 도착할 수 있는 경우의 수는 정보관에서 출발과 동시에 도착하는 경우 1개이다.

 

2. 1분

전산관은 [정보관, 미래관, 신양관]과 이어져있다.

미래관은 [정보관, 전산관, 신양관, 한경직]과 이어져있다.

 

1분째에 전산관에 도착하는 경우의 수 = 0분 째에 [정보관, 미래관, 신양관]에 도착하는 경우의 수들의 합 = [1+0+0]  = 1

1분째에 미래관에 도착하는 경우의 수 = 0분 째에 [정보관, 전산관, 신양관, 한경직]에 도착하는 경우의 수들의 합 = [1+0+0+0] = 1

 

3. 2분

정보관은 [전산관, 미래관]과 이어져있다.

전산관은 [정보관, 미래관, 신양관]과 이어져있다.

미래관은 [정보관, 전산관, 신양관, 한경직]과 이어져있다.

신양관은 [전산관, 미래관, 한경직, 진리관]과 이어져있다.

 

2분째에 정보관에 도착하는 경우의 수 = 1분 째에 [전산관, 미래관]에 도착하는 경우의 수들의 합 = [1+1] = 2

2분째에 전산관에 도착하는 경우의 수 = 1분 째에 [정보관, 미래관, 신양관]에 도착하는 경우의 수들의 합 = [0+1+0] = 1

2분째에 미래관에 도착하는 경우의 수 = 1분 째에 [정보관, 전산관, 신양관, 한경직]에 도착하는 경우의 수들의 합 = [0+1+0+0] = 1

2분째에 신양관에 도착하는 경우의 수 = 1분 째에 [전산관, 미래관, 한경직, 진리관]에 도착하는 경우의 수들의 합 = [1+1+0+0] = 2

...(중략)

 

위와 같이, '이 건물에 오기 1분 전, 연결된 건물들에서의 경우의 수를 모두 더하면' 현재 건물의 경우의 수를 구할 수 있다.

 

코드

D = int(input())

DP = [[0] * (D+1) for _ in range(8)]
# Index // 0: 정보관 1:전산관 2:미래관 3:신양관 4:한경직 5:진리관 6:형남공학관 7:학생회관
DP[0][0] = 1
for i in range(1, D+1):
    DP[0][i] = (DP[1][i-1] + DP[2][i-1]) % 1000000007
    # 정보관 = 전산관+미래관
    DP[1][i] = (DP[0][i-1] + DP[2][i-1] + DP[3][i-1]) % 1000000007
    # 전산관 = 정보관+미래관+신양관
    DP[2][i] = (DP[0][i-1] + DP[1][i-1] + DP[3][i-1] + DP[4][i-1]) % 1000000007
    # 미래관 = 정보관+전산관+신양관+한경직
    DP[3][i] = (DP[1][i-1] + DP[2][i-1] + DP[4][i-1] + DP[5][i-1]) % 1000000007
    # 신양관 = 전산관+미래관+한경직+진리관
    DP[4][i] = (DP[2][i-1] + DP[3][i-1] + DP[5][i-1] + DP[6][i-1]) % 1000000007
    # 한경직 = 미래관+신양관+진리관+형남
    DP[5][i] = (DP[3][i-1] + DP[4][i-1] + DP[7][i-1]) % 1000000007
    # 진리관 = 신양관+한경직+학생회관
    DP[6][i] = (DP[4][i-1] + DP[7][i-1]) % 1000000007
    # 형남 = 한경직+학생회관
    DP[7][i] = (DP[5][i-1] + DP[6][i-1]) % 1000000007
    # 학생회관 = 진리관+형남공학관

print(DP[0][D])

여담

우리 학교가 나오는 문제를 보니 기분이 묘하다. 정보섬의 애환이 느껴지는 문제다.