백준 2667(파이썬):단지번호붙이기
백준 2667번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/2667
문제 내용
나의 풀이
import sys
from collections import deque
# input=sys.stdin.readline
def bfs(sx,sy):
queue=deque()
queue.append((sx,sy))
house_num=1
while queue:
x,y=queue.popleft()
for i in range(4):
rx,ry=x+dx[i],y+dy[i]
if 0<=rx<n and 0<=ry<n and visited[rx][ry]==0 and map[rx][ry]==1:
visited[rx][ry]=1
queue.append((rx,ry))
house_num+=1
house.append(house_num)
def solve():
global count
for i in range(n):
for j in range(n):
if map[i][j]==1 and visited[i][j]==0:
sx,sy=i,j
visited[sx][sy]=1
bfs(sx,sy)
count+=1
house.sort()
n=int(input())
map=[list(map(int,input())) for _ in range(n)]
visited=[[0]*n for _ in range(n)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
count=0
house=[]
solve()
print(count)
for i in house:
print(i)
- 우선 단지의 수와 단지내 집의 개수를 저장할 변수 count, house를 선언
- 그 후, 시작점을 찾아 BFS탐색을 하여 단지의 수와 단지내의 아파트 수를 저장하도록 했다.
처음에는 단지내의 아파트 수가 아니라 BFS탐색시의 레벨 값을 넣어버렸다… 하지만 다시 본 결과 queue에 들어가는 좌표들의 수를 넣어주면 단지내의 아파트 수가 된다.
풀이를 본 후
BFS의 풀이는 보통 내 풀이와 비슷했다..
해결한 후
BFS 문제에 점점 익숙해지는 느낌이다… DFS의 풀이 방법도 있으니 숙지해놓으면 좋을것 같다..
