โ๋ฌธ์
https://www.acmicpc.net/problem/1068
์ฑ๋ฅ ์์ฝ
๋ฉ๋ชจ๋ฆฌ: 34936 KB, ์๊ฐ: 64 ms
๋ถ๋ฅ
๊น์ด ์ฐ์ ํ์, ๊ทธ๋ํ ์ด๋ก , ๊ทธ๋ํ ํ์, ํธ๋ฆฌ
๋ฌธ์ ์ค๋ช
ํธ๋ฆฌ์์ ๋ฆฌํ ๋ ธ๋๋, ์์์ ๊ฐ์๊ฐ 0์ธ ๋ ธ๋๋ฅผ ๋งํ๋ค.
ํธ๋ฆฌ๊ฐ ์ฃผ์ด์ก์ ๋, ๋ ธ๋ ํ๋๋ฅผ ์ง์ธ ๊ฒ์ด๋ค. ๊ทธ ๋, ๋จ์ ํธ๋ฆฌ์์ ๋ฆฌํ ๋ ธ๋์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ ธ๋๋ฅผ ์ง์ฐ๋ฉด ๊ทธ ๋ ธ๋์ ๋ ธ๋์ ๋ชจ๋ ์์์ด ํธ๋ฆฌ์์ ์ ๊ฑฐ๋๋ค.
์๋ฅผ ๋ค์ด, ๋ค์๊ณผ ๊ฐ์ ํธ๋ฆฌ๊ฐ ์๋ค๊ณ ํ์.
ํ์ฌ ๋ฆฌํ ๋ ธ๋์ ๊ฐ์๋ 3๊ฐ์ด๋ค. (์ด๋ก์ ์์น ๋ ๋ ธ๋) ์ด๋, 1๋ฒ์ ์ง์ฐ๋ฉด, ๋ค์๊ณผ ๊ฐ์ด ๋ณํ๋ค. ๊ฒ์ ์์ผ๋ก ์์น ๋ ๋ ธ๋๊ฐ ํธ๋ฆฌ์์ ์ ๊ฑฐ๋ ๋ ธ๋์ด๋ค.
์ด์ ๋ฆฌํ ๋ ธ๋์ ๊ฐ์๋ 1๊ฐ์ด๋ค.
โ๐ปํ์ด
์ธ์ ๋ฆฌ์คํธ๋ ์ฌ์ ํ์ ํ์ฉํ์ฌ ๊ฐ ๋ ธ๋ ๋ณ ์์ ๋ ธ๋๋ฅผ ๊ธฐ๋กํ๋ค.
์ด์ ์ง์ฐ๊ณ ์ ํ๋ ๋ ธ๋๋ฅผ ์ญ์ ํด์ผ ํ๋ค. ์ง์ฐ๋ ค๋ ๋ ธ๋์ ์์ ๋ ธ๋๊ฐ ์์ ์ ์๊ธฐ ๋๋ฌธ์ ๊น์ด ์ฐ์ ํ์์ผ๋ก ์์ ๋ ธ๋๋ฅผ ํ์ํ๋ค. ๋ง์ฝ ์ง์ฐ๋ ค๋ ๋ ธ๋์ ์์ ๋ ธ๋๊ฐ ์๊ณ ๊ทธ ์์ ๋ ธ๋์ ๋ ์์ ๋ ธ๋๊ฐ ์๋ค๋ฉด ๋ ์ด์ ์์ ๋ ธ๋๊ฐ ์์ ๋๊น์ง ํ์ํ๋ค. ์์ ๋ ธ๋๊ฐ ์๋ค๋ฉด ์ด์ ๋ ธ๋๋ฅผ ํธ๋ฆฌ์์ ์ญ์ ํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ต์ข ์ ์ผ๋ก ์ ๊ฑฐํ๋ ค๋ ๋ ธ๋๋ ํธ๋ฆฌ์์ ์ญ์ ํ๋ค. ์ด๋, ๋ ธ๋๋ฅผ ์ ๊ฑฐํ๋ฉฐ ๋ฐฉ๋ฌธํ ๋ ธ๋๋ค์ ํ์ํ๋ค.
๋ ธ๋๋ฅผ ๋ค ์ญ์ ํ์ผ๋ ๋ฆฌํ ๋ ธ๋์ ๊ฐ์๋ฅผ ๊ตฌํ๋ฉด ๋๋ค. ์ฐ์ ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋์ธ์ง ํ์ธํ๋ค. ์ฌ๊ธฐ์ ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋๋ ์ง์์ง์ง ์๊ณ ๋จ์์๋ ๋ ธ๋๋ค์ ์๋ฏธํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋๊ฐ ํธ๋ฆฌ์ ์๋ค๋ฉด ์์ ๋ ธ๋๊ฐ ์๋ ๊ฒ์ด๋ฏ๋ก res + 1์ ํ๋ค. ์ด๋, ํธ๋ฆฌ ์์ ๋จ์์๋ ๋ ธ๋์ ์์ ๋ ธ๋์ ์ง์ฐ๊ณ ์ ํ๋ ์์ ๋ ธ๋๊ฐ ๋จ์์๋ค. ๊ทธ๋ฌ๋ฏ๋ก ์ด๋ฅผ ์ ์ธํ๊ณ ๋จ์์๋ ์์์ ์๊ฐ 0์ด๋ฉด res + 1์ ํ๋ฉด ๋๋ค.
๐ป์ฝ๋
import sys
from collections import defaultdict
input = sys.stdin.readline
N = int(input())
nodes = list(map(int, input().split()))
remove = int(input())
tree = defaultdict(list)
visited = [False] * N
def dfs(r):
visited[r] = True
for n in tree[r]:
if not tree[n]:
visited[n] = True
tree.pop(n)
else:
dfs(n)
tree.pop(r)
for v in range(N):
if nodes[v] == -1:
continue
tree[nodes[v]].append(v)
dfs(remove)
res = 0
for n in range(N):
if not visited[n]:
if remove in tree[n] and len(tree[n])-1 == 0:
res +=1
if not tree[n]:
res += 1
print(res)
๐ํ๊ธฐ
์ง์ง ๋ฐ๋ก ์๊ฐํ๋ ๊ฒ์ด ๋งค์ฐ ์ค์ํ ๊ฒ ๊ฐ๋ค. ๋งค๋ฒ ํ ์คํธ์ผ์ด์ค๋ง ํต๊ณผํ๋ฉด ์ ์ถํด์ ๊ณ์ ๋จ์ด์ง๋๋ณด๋ค..๐ฅฒ
๊ทธ๋ฆฌ๊ณ ์ผ์ฑ ์ฝํ ์ ๊ฒฝ์ฐ pypy3์ธ ๊ฑธ๋ก ์๊ณ ์์ด pypy3๋ก๋ ์ ์ถํด๋ณด์๋ค.๋ฉ๋ชจ๋ฆฌ๊ฐ ๋๋ฌด ์ฐจ์ด๋๋๋ฐ ์ด๋ป๊ฒ ์ค์ด๋ฉด ์ข์์ง..
'Coding Test > Algorithms' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 1158. ์์ธํธ์ค ๋ฌธ์ /Python - Silver4 (0) | 2025.04.01 |
---|---|
[๋ฐฑ์ค] 1966. ํ๋ฆฐํฐ ํ/Python - Silver3 (0) | 2025.03.18 |
[๋ฐฑ์ค] 2800. ๊ดํธ ์ ๊ฑฐ/Python - Gold4 (0) | 2025.03.18 |
[๋ฐฑ์ค]14940. ์ฌ์ด ์ต๋จ๊ฑฐ๋ฆฌ/Python - Silver1 (0) | 2025.03.10 |
[๋ฐฑ์ค] 17298.์คํฐ์/Python - Gold4 (0) | 2025.03.07 |