BOJ-백준 2667번 단지번호붙이기

BOJ-백준 2667번 단지번호붙이기 

링크 : https://www.acmicpc.net/problem/2667

 

 

2667번: 단지번호붙이기

문제

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

 

 

✅ Python 정답 코드 입니다.

import sys
sys.setrecursionlimit(10**6)

def dfs(i,j):
  if i<0 or j<0 or i> n-1 or j>n-1:
    return
  if field[i][j] == 0:
    return 
  field[i][j]=0
  visited.append((i,j))
  dfs(i,j-1)
  dfs(i,j+1)
  dfs(i-1,j)
  dfs(i+1,j)
  return

n = int(input())
field = []
visited = []
for _ in range(n):
  x = list(map(int,input()))
  field.append(x)
house = []
houseGroup = 0
for i in range(n):
  for j in range(n):
    if field[i][j]==1:
      dfs(i,j)
      houseGroup+=1
      house.append(len(visited))
      visited = []
print(houseGroup)
for h in sorted(house):
  print(h)
if not house:
  print(0)

 

 

📌 해설

DFS를 수행해 graph를 탐색합니다. 인접한 집들을 묶어 단지(houseGroup) 수를 증가 시킵니다. 그동안 방문된 집들의 수를 house에 append시켜서 단지내의 집 수를 저장합니다. 저장한 visited는 append된 직후 비워져서 새 단지에 방문된 집들의 좌표를 저장합니다. 

 

🚩 주의

각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력해야 하기 때문에 house 리스트를 정렬하는 과정이 필요합니다. 25*25 까지 입력이 되기 때문에 재귀호출의 깊이 제한을 변경합니다. 

 

def dfs(i,j):
  if i<0 or j<0 or i> n-1 or j>n-1:
    return
  if field[i][j] == 0:
    return 
  field[i][j]=0
  visited.append((i,j))
  dfs(i,j-1)
  dfs(i,j+1)
  dfs(i-1,j)
  dfs(i+1,j)
  return

1. 상하좌우를 이동하는 dfs를 작성합니다.

1-1. 상하좌우를 이동하다가 field를 벗어나면 탐색을 종료시킵니다.

1-2. field에 집이 없으면 (0) 탐색을 종료합니다.

1-3. field에 집이 발견되면 방문표시를 합니다.(1->0)

1-4. visited에 방문한 집의 좌표를 append시킵니다. 

1-5. 상하좌우를 이동하는 dfs를 재귀호출 합니다. 

 

n = int(input())
field = []
visited = []
for _ in range(n):
  x = list(map(int,input()))
  field.append(x)
house = []
houseGroup = 0

2. field를 입력받고 필요한 변수를 초기화 합니다. 

2-1. n : 필드의 크기, field n*n

2-2. field : 집의 정보를 저장

2-3. visited : 방문한 집의 좌표를 저장 -> visited의 길이를 통해 집의 수를 구한다

2-4. house : 집의 수를 저장한다 -> 오름차순으로 정렬한 뒤 출력해야 한다.

2-5. houseGroup : 단지 수를 저장한다. 

 

for i in range(n):
  for j in range(n):
    if field[i][j]==1:
      dfs(i,j)
      houseGroup+=1
      house.append(len(visited))
      visited = []

3. field를 모두 조회하는 이중 for문을 작성합니다.

3-1. 집이 발견되면(1) dfs 탐색을 시작합니다. 

3-2. dfs 탐색이 끝나면 houseGroup을 증가 시킵니다. 

3-3. house에 하나의 단지를 탐색한 visited에 저장된 집들의 수를 저장합니다. 

3-4. visited를 비워줌으로써 다음 houseGroup에 방문할 수 있도록 초기화합니다. 

print(houseGroup)
for h in sorted(house):
  print(h)
if not house:
  print(0)

4. 결과를 출력합니다.

4-1. houseGroup을 출력합니다.

4-2. 정렬된(sorted)house를 차례대로 출력합니다. 

4-3. 만약 house가 빈 list이면 (집이 하나도 없으면) 0을 출력합니다.

 

 

::