[BOJ 2667번] 단지번호붙이기

1. 문제

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

 

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

 

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

 

---

 

2. 문제 풀이

1) bfs로 문제 풀기 

• 이중 반복문을 통해 maps[x][y] == 1인 곳을 발견하면 bfs함수를 호출한다.
• bfs함수에서 단지 내에 있는 가구의 개수를 확인한다. 이때, 방문한 가구는 0으로 표시하여 다시 방문하지 않도록 한다. (+ 다른 단지로 착각하지 않도록 하게 한다) 
• 각 단지의 가구 수를 APT 리스트에 추가한다. 

import sys
from collections import deque

def bfs(maps, x, y):
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    queue = deque([(x, y)])
    count = 1
    while queue:
        x, y = queue.popleft()
        
        for dx, dy in directions:
            nx, ny = x+dx, y+dy
            
            if 0<=nx<len(maps) and 0<=ny<len(maps) and maps[nx][ny] == 1:
                maps[nx][ny] = 0 
                queue.append((nx, ny))
                count +=1
                
    return count 
    

N = int(sys.stdin.readline())
maps = []
APT = []
for i in range(N):
    maps.append(list(map(int, sys.stdin.readline().rstrip())))
    
for x in range(N):
    for y in range(N):
        if maps[x][y] == 1:
            maps[x][y] = 0
            APT.append(bfs(maps, x, y))

print(len(APT))           
for i in sorted(APT):
    print(i)

 

 

2) dfs로 문제 풀기

• 이중 반복문을 통해 maps[x][y] == 1인 곳을 발견하면 count를 0으로 초기화하고 dfs함수를 호출한다.
• 상하좌우로 움직였을 때, 가구가 존재한다면 연결된 다른 가구를 찾기 위해 다시 dfs함수를 호출한다. 

import sys
from collections import deque

def dfs(maps, x, y):
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    global count 
    count +=1
    
    for dx, dy in directions:
        nx, ny = x+dx, y+dy
            
        if 0<=nx<len(maps) and 0<=ny<len(maps) and maps[nx][ny] == 1:
            maps[nx][ny] = 0 
            dfs(maps, nx, ny)
                
    return count 
    

N = int(sys.stdin.readline())
maps = []
APT = []
global count
for i in range(N):
    maps.append(list(map(int, sys.stdin.readline().rstrip())))
    
for x in range(N):
    for y in range(N):
        if maps[x][y] == 1:
            maps[x][y] = 0
            count = 0
            APT.append(dfs(maps, x, y))

print(len(APT))           
for i in sorted(APT):
    print(i)

 

다 풀고 곰곰이 생각을 해보니..

global변수인데 왜...return을 했을까....? 글로벌 선언을 안하고 count를 매개변수로 받거나 아니면 글로벌 선언하고 return 하던가...나중에 수정해야지 

 

진짜 이제 확실히 dfs랑 bfs 감 많이 잡은듯?? 문제 많이 풀어보는게 좋다..