단지번호붙이기(백준 2667번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가? ✓

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

---

난이도 체감

1. 최상

2. 상✓

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

나의 풀이

import sys
from collections import deque

def BFS(houses,x,y,visited,N):
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    visited[x][y]=True
    h_or_n=houses[x][y]
    queue=deque()
    queue.append((x,y))
    count=1
    while queue:
        v=queue.popleft()
        for i in range(4):
            mx=v[0]+dx[i]
            my=v[1]+dy[i]
            if 0<=mx<N and 0<=my<N and not visited[mx][my] and houses[mx][my]==h_or_n:
                visited[mx][my]=True
                queue.append((mx,my))
                count+=1
    return count
N=int(input())       
houses=[]
visited=[[False]*N for _ in range(N)]
for _ in range(N):
    l=list(sys.stdin.readline().strip())
    l=list(map(int,l))
    houses.append(l)
total_count=0
answer=[]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            if houses[i][j]==1:
                total_count+=1
                answer.append(BFS(houses,i,j,visited,N))
            else:
                BFS(houses,i,j,visited,N)
answer.sort()
print(total_count)
for ans in answer:
    print(ans)

• 0(단지가 아닌 곳)이든 1(단지인 곳)이든, BFS를 통해 연결된 영역을 찾아 visited를 True로 바꿔주었다. 그 중에서 houses가 1인 곳에서 출발한 곳의 개수만 유지하여 answer에 넣어주었다. 이것이 연결된 단지의 총 개수이다. 각 단지의 개수들을 answer에 넣어주고, sort()하여 차례로 출력하였다.

수정한 정답(0에 대한 BFS x)

import sys
from collections import deque

def BFS(houses,x,y,visited,N):
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    visited[x][y]=True
    h_or_n=houses[x][y]
    queue=deque()
    queue.append((x,y))
    count=1
    while queue:
        v=queue.popleft()
        for i in range(4):
            mx=v[0]+dx[i]
            my=v[1]+dy[i]
            if 0<=mx<N and 0<=my<N and not visited[mx][my] and houses[mx][my]==h_or_n:
                visited[mx][my]=True
                queue.append((mx,my))
                count+=1
    return count
N=int(input())       
houses=[]
visited=[[False]*N for _ in range(N)]
for _ in range(N):
    l=list(sys.stdin.readline().strip())
    l=list(map(int,l))
    houses.append(l)
total_count=0
answer=[]
for i in range(N):
    for j in range(N):
        if not visited[i][j] and houses[i][j]==1:
            total_count+=1
            answer.append(BFS(houses,i,j,visited,N))
answer.sort()
print(total_count)
for ans in answer:
    print(ans)

• 생각해보니, if not visited[i][j] and houses[i][j]==1: 조건을 사용하면, 굳이 0에 대한 그룹을 찾지 않아도 괜찮았다. 조금 더 효율있는 코드를 작성할 수 있는 것