|
์ฝ๋ ์์ฑํ๊ธฐ
def solution(n, results):
answer=0
graph=[[0]*n for _ in range(n)]
for i, j in results :
graph[i-1][j-1]=1
graph[j-1][i-1]=-1
for k in range(n) :
for i in range(n) :
for j in range(n) :
if i==j or graph[i][j] in [-1, 1] :
continue
if graph[i][k]==graph[k][j]==1 :
graph[i][j]=1
graph[j][i]=graph[j][k]=graph[k][i]=-1
for row in graph :
if row.count(0)==1 :
answer+=1
return answer
Python
๋ณต์ฌ
|
์ฝ๋ ์ค๋ช
ํ๊ธฐ
1.
graph[i][j]์์ i๊ฐ j๋ฅผ ์ด๊ธด ๊ฒฝ์ฐ๋ 1, i๊ฐ j์๊ฒ ์ง ๊ฒฝ์ฐ๋ -1๋ก ์ ์ฅํ๋ค.
2.
results ๋ฆฌ์คํธ์ ์๋ ๊ฒฐ๊ณผ๋ฅผ graph์ ๋ฐ์ํ๋ค.
3.
์ค๊ฐ์ง์ k๋ฅผ ๊ฑฐ์น๋ฉด์ graph[i][k]=1์ด๊ณ graph[k][j]=1์ด๋ฉด i๋ j๋ฅผ ์ด๊ฒผ๊ธฐ ๋๋ฌธ์ graph[i][j]=1์ ์ ์ฅํ๋ค. ๋ฐ๋์ ๊ฒฝ์ฐ๋ ๊ฒฝ๊ธฐ์์ ์ก๊ธฐ ๋๋ฌธ์ -1์ ์ ์ฅํ๋ค.
4.
ํ์ ๋๋ฉด์ ์๊ธฐ์์ ์ ์ ์ธํ๊ณ ๋ ์ด๊ธฐ๊ฑฐ๋ ์ง ๊ฒฐ๊ณผ๊ฐ ์์ด์ผํ๊ธฐ ๋๋ฌธ์ 0์ ๊ฐ์๊ฐ 1์ด๋ฉด answer๋ฅผ 1 ์ฆ๊ฐ ์ํจ๋ค.