Search

๊น€๋ฏผ์ง€

2.๋ฌธ์ œ์ด๋ฆ„
3. ์ˆ˜ํ–‰์‹œ๊ฐ„[์ดˆ(s)]
900
์ข‹์•„์š” ๋ˆ„๋ฅด๊ธฐ
์ข‹์•„์š” ์ˆ˜
: 0
5 more properties
| ์ฝ”๋“œ ์ž‘์„ฑํ•˜๊ธฐ
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 ์ฆ๊ฐ€ ์‹œํ‚จ๋‹ค.