๐ ๊ฒฝ๋ก ์ฐพ๊ธฐ
๋ฐฑ์ค Class3 Silver1
solved_ac[Class3] ๊ฒฝ๋ก ์ฐพ๊ธฐ
๋ฌธ์
๊ฐ์ค์น ์๋ ๋ฐฉํฅ ๊ทธ๋ํ G๊ฐ ์ฃผ์ด์ก์ ๋, ๋ชจ๋ ์ ์ (i, j)์ ๋ํด์, i์์ j๋ก ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์๋์ง ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N (1 โค N โค 100)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ ์ค์๋ ๊ทธ๋ํ์ ์ธ์ ํ๋ ฌ์ด ์ฃผ์ด์ง๋ค. i๋ฒ์งธ ์ค์ j๋ฒ์งธ ์ซ์๊ฐ 1์ธ ๊ฒฝ์ฐ์๋ i์์ j๋ก ๊ฐ๋ ๊ฐ์ ์ด ์กด์ฌํ๋ค๋ ๋ป์ด๊ณ , 0์ธ ๊ฒฝ์ฐ๋ ์๋ค๋ ๋ป์ด๋ค. i๋ฒ์งธ ์ค์ i๋ฒ์งธ ์ซ์๋ ํญ์ 0์ด๋ค.
์ถ๋ ฅ
์ด N๊ฐ์ ์ค์ ๊ฑธ์ณ์ ๋ฌธ์ ์ ์ ๋ต์ ์ธ์ ํ๋ ฌ ํ์์ผ๋ก ์ถ๋ ฅํ๋ค. ์ ์ i์์ j๋ก ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์์ผ๋ฉด i๋ฒ์งธ ์ค์ j๋ฒ์งธ ์ซ์๋ฅผ 1๋ก, ์์ผ๋ฉด 0์ผ๋ก ์ถ๋ ฅํด์ผ ํ๋ค.
์์ ์ ๋ ฅ 1
3
0 1 0
0 0 1
1 0 0
์์ ์ถ๋ ฅ 1
1 1 1
1 1 1
1 1 1
์์ ์ ๋ ฅ 2
7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0
์์ ์ถ๋ ฅ 2
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0
๐ ์๋ฃ๊ตฌ์กฐ
Visited ๋ฐฐ์ด โก๏ธ index ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ์๋์ง๋ฅผ ์๋ ค์ฃผ๋ ๋ฐฐ์ด
์ด ๋ฌธ์ ๊ฐ ๋ฌป๊ณ ์ ํ๋ ์์ง๋ฅผ ํ ๋ง๋๋ก ์ ๋ฆฌํ๋ฉด
โํน์ ๋ ธ๋๋ก๋ถํฐ ๊ทธ๋ํ ํ์์ ์งํํ์์ ๋, ๋ฐฉ๋ฌธํ ์ ์๋ ๋ ธ๋๋?โ
๋ฐ๋ผ์, 0๋ฒ ๋ ธ๋๋ถํฐ N-1๋ฒ ๋ ธ๋๊น์ง ๊ฐ๊ฐ ๊ทธ๋ํ ํ์์ ํ์ฌ Visited ๋ฐฐ์ด์ ๋ฝ์์ฃผ๋ฉด ๋๋ค.
๐จ๐ปโ๐ป CODE
from collections import deque
N = int(input())
graph = [[0]*N for _ in range(N)]
for i in range(N):
line = input().replace(" ","")
for j in range(N):
graph[i][j] = int(line[j])
def bfs(start):
visited = [0]*N
q = deque([start])
while q:
cur = q.popleft()
for i in range(N):
if graph[cur][i] == 1 and visited[i] == 0:
q.append(i)
visited[i] = 1
return visited
for node in range(N):
print(*bfs(node))