【AtCoder】ABC204를 Python3로 해설

ABC204의 해설.

A - Rock-paper-scissors

해설

3명이 싸우고 아이코가 되었다. 두 손에서 또 다른 손을 추측하는 문제.
0 는 구, 1 는 조키를, 2 는 파로 하면, 전체의 합계가 3 이 되므로, 2명의 손을 당긴 것이 또 1명의 손이 된다.

또, 전원 같은 손의 경우는, 누군가 1명의 손을 출력하면 된다.

코드

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

if x != y:
    print(3-(x+y))
else:
    print(x)

B - Nuts

해설

어떤 나무의 열매가 10개 이상 있으면, 10개 남기고 전부 취한다. 이것을 N그루의 나무에 대해서 행하는 문제.
코드도 그대로, 나무의 열매 a 가 10 보다 크면, a-10 한 값을 cnt 에 더한다.

코드

N = int(input())
A = map(int, input().split())
cnt = 0

for a in A:
    if a >= 10:
        cnt += a-10

print(cnt)

C - Tour

해설

스타트 지점을 고정했을 때 골 지점으로 할 수 있는 도시의 개수를 세는 문제.
이 문제는 DFS(깊이 우선 탐색)나 BFS(폭 우선 탐색)에서 구할 수 있다. 이번에는 공식 해설을 축으로 DFS로 해설해 나간다.

DFS에 대해 원래 모르는 분은 이 기사를 먼저 보시고 싶다.

코드를 따라 설명하고 싶으므로 먼저 코드.

# おまじない
import sys
sys.setrecursionlimit(10000)

# 入力の読み込み
N, M = map(int, input().split())
G = [[] for _ in range(N)]

# G[i] は都市iから道路で直接繋がっている都市のリスト
for _ in range(M):
    A, B = map(int, input().split())
    # Pythonではindex0始まりなので、都市iを-1して揃える
    G[A-1].append(B-1)

# 深さ優先探索（dfs）


def dfs(v):
    if seen[v]:
        return  # 同じ頂点を2度以上調べないためのreturn

    # 初期値でスタートをゴール地として設定 ex)(1, 1)をTrue
    seen[v] = True

    for vv in G[v]:
        dfs(vv)


ans = 0

# 都市iからスタートする場合
for i in range(N):
    # チェッカー
    seen = [False]*N
    # seen[j] は都市jに到達可能かどうかを表す
    dfs(i)
    # 都市iからの組み合わせ（True）の合計
    ans += sum(seen)

print(ans)

알기 쉽게 입력 예를 나타내면서 설명한다. 입력 예는

5 4
1 2
2 3
2 4
1 5

그림에서 보면 다음과 같습니다.



우선, 초기치 설정으로서 G 를 만든다. G 은 Graph G . 이것을 도시의 수 N 만 리스트를 만들고 싶기 때문에, 다음과 같이 쓴다.

G = [[] for _ in range(5)]

output
>> G: [[], [], [], [], []]

다음에, A, B 의 연결을 입력하는 것이지만, i 가 원래 0 스타트이므로, 초기치 $A_1$, $B_i$ 와 값이 어긋나 버린다. 따라서 i-1 를 사용하여 취급하기 쉬운 형태로 정돈한다.

for _ in range(4):
    A, B = map(int, input().split())
    G[A-1].append(B-1)

output
>> G: [[1, 4], [2, 3], [], [], []]

def dfs(): 는 건너뛰고 for 설명에서. i 에 스타트가 되는 도시를 넣는다. 여기서, 체커로서, seen 를 써 둔다.

for i in range(4):
    seen = [False]*4
    ...

output
>> seen: [False, False, False, False]

이야기의 대근이 되는, DFS(깊이 우선 탐색). 우선, seen[v] = True 하지만, 예를 들어, 이 입력예이면 우선, v = 0 (도시 1)이 들어간다. 따라서, seen: [True, False, False, False] 가 되어, (1, 1) 의 판정이 된다.
다음으로 도시 1과의 연결을 보고 싶다. 그림을 보면 도시 1과 연결되어 있는 것은 도시 2와 도시 5이다. 이것은 G에 값이 저장되어 있으므로 여기에서 참조하십시오. 따라서, G[i-1] 가 되는 G[0] 에 대해 루프를 돌린다.
이 때 같은 정점으로 돌리지 않게, if seen[v]: return 로 seen[v] 가 True 이면, 끝낸다.
dfs(0) 때, 즉, 도시 1의 스타트와 골의 조합이지만, 보통으로 생각하면, 도시 1-5까지, 어느 도시에서도 조합으로서 생각된다. 바로 그대로, 이때의 seen 는, seen: [True, True, True, True, True] 가 되어 있다. 따라서 이것을 sum() 덧붙여 주면 조합을 계산할 수 있다.
dfs(1) 때, 즉 도시 2의 시작과 목표의 조합은 도시 2-4까지가 대답이다. 이때의 seen 는 seen: [False, True, True, True, False] 로 제대로 대응한 대답이 되고 있다.

이것을 전 dfs(i) 로 계산해, 계산한 ans 가 대답이 된다.

코드

import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    G[A-1].append(B-1)


def dfs(v):
    if seen[v]:
        return

    seen[v] = True

    for vv in G[v]:
        dfs(vv)

ans = 0

for i in range(N):
    seen = [False]*N
    dfs(i)
    ans += sum(seen)

print(ans)

편집 후기

공식 해설은 전혀 알기 쉬운 해설이 되지 않은 것 같은....