๐ ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ
๋ฐฑ์ค Class3 Silver1
solved_ac[Class3] ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ
๋ฌธ์
<๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ์ ์ฌ๊ฐํ ๋ชจ์์ ์ง๋๊ฐ ์๋ค. 1์ ์ง์ด ์๋ ๊ณณ์, 0์ ์ง์ด ์๋ ๊ณณ์ ๋ํ๋ธ๋ค. ์ฒ ์๋ ์ด ์ง๋๋ฅผ ๊ฐ์ง๊ณ ์ฐ๊ฒฐ๋ ์ง์ ๋ชจ์์ธ ๋จ์ง๋ฅผ ์ ์ํ๊ณ , ๋จ์ง์ ๋ฒํธ๋ฅผ ๋ถ์ด๋ ค ํ๋ค. ์ฌ๊ธฐ์ ์ฐ๊ฒฐ๋์๋ค๋ ๊ฒ์ ์ด๋ค ์ง์ด ์ข์ฐ, ํน์ ์๋์๋ก ๋ค๋ฅธ ์ง์ด ์๋ ๊ฒฝ์ฐ๋ฅผ ๋งํ๋ค. ๋๊ฐ์ ์์ ์ง์ด ์๋ ๊ฒฝ์ฐ๋ ์ฐ๊ฒฐ๋ ๊ฒ์ด ์๋๋ค. <๊ทธ๋ฆผ 2>๋ <๊ทธ๋ฆผ 1>์ ๋จ์ง๋ณ๋ก ๋ฒํธ๋ฅผ ๋ถ์ธ ๊ฒ์ด๋ค. ์ง๋๋ฅผ ์ ๋ ฅํ์ฌ ๋จ์ง์๋ฅผ ์ถ๋ ฅํ๊ณ , ๊ฐ ๋จ์ง์ ์ํ๋ ์ง์ ์๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์๋ ์ง๋์ ํฌ๊ธฐ N(์ ์ฌ๊ฐํ์ด๋ฏ๋ก ๊ฐ๋ก์ ์ธ๋ก์ ํฌ๊ธฐ๋ ๊ฐ์ผ๋ฉฐ 5โคNโค25)์ด ์ ๋ ฅ๋๊ณ , ๊ทธ ๋ค์ N์ค์๋ ๊ฐ๊ฐ N๊ฐ์ ์๋ฃ(0ํน์ 1)๊ฐ ์ ๋ ฅ๋๋ค.
์ถ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์๋ ์ด ๋จ์ง์๋ฅผ ์ถ๋ ฅํ์์ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ ๋จ์ง๋ด ์ง์ ์๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ์์ค.
์์ ์ ๋ ฅ 1
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
์์ ์ถ๋ ฅ 1
3
7
8
9
๐ ์๋ฃ๊ตฌ์กฐ
BFS๋ฅผ ์ฌ์ฉํ์ฌ ํ์๋ค. ํน์ 1 ๋ ธ๋๋ฅผ ๊ธฐ์ ์ผ๋ก ํ์ฌ ๋ ์ด์ 1์ด ์ ๋์ฌ๋๊น์ง ์์ ํ์์ ํ๋ ๊ฒ์ด๊ธฐ ๋๋ฌธ์ DFS,BFS ๋ฌด์์ ์ ํํ๋ ์๊ด ์์๋ค.
๋๋ visited ๋ฐฐ์ด์ ๋ฐ๋ก ์์ฑํ์ง ์๊ณ ๊ทธ๋ํ ์์ฒด ๋ด์์ ํด๊ฒฐํ์๋ค.
๋ง์ง๋ง ์ค๋ฆ์ฐจ์ ์ ๋ ฌ๊น์ง ๊ณ ๋ คํ์ฌ ์ง 9๊ฐ๋ถํฐ ํ์ํ๋ค๊ณ ๊ฐ์ ํ์๋ค.
๊ทธ๋ํ์ ์ฒ์๋ถํฐ ๋๊น์ง 1์ธ ๋ ธ๋๋ค์ ํ์ํ๋ฉฐ 2๋ก ๋ฐ๊ฟ์ค๋ค. ๊ทธ๋ฆฌ๊ณ BFSํ์์ด ์ข ๋ฃ๋์์ผ๋ฉด ์ต์ข ์ง์ ๊ฐ์๋ฅผ ์ ๋ต ๋ฐฐ์ด์ ์ถ๊ฐํ๋ค.
๊ทธ๋ ๊ฒ ํด์ ๋์จ ์ ๋ต ๋ฐฐ์ด์ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ ์ํจ ํ, ์ ๋ต์ ํ์์ ๋ง๊ฒ ์ถ๋ ฅํ๋ค.
๐จ๐ปโ๐ป CODE
from collections import deque
n = int(input())
graph = [[0]*n for _ in range(n)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for i in range(n):
house_info = input()
for j in range(n):
graph[i][j] = int(house_info[j])
def bfs(x,y):
house_count = 0
q = deque([[x,y]])
graph[x][y] = 2
while q:
cur_node = q.popleft()
house_count += 1
for i in range(4):
new_x = cur_node[0]+dx[i]
new_y = cur_node[1]+dy[i]
if 0<=new_x<n and 0<=new_y<n:
if graph[new_x][new_y] == 1:
q.append([new_x,new_y])
graph[new_x][new_y] = 2
return house_count
lst_answer = []
for x in range(n):
for y in range(n):
if graph[x][y] == 1:
lst_answer.append(bfs(x,y))
lst_answer.sort()
print(len(lst_answer))
for answer in lst_answer:
print(answer)