[DFS/BFS] BOJ 2667 - 단지번호붙이기 / python

문제링크

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

문제

입출력

💡 사고의 흐름

• 입력 > 지도크기, 행렬 입력받음 (행렬 입력받는 과정에서, apart =[]로 한 후, 한 줄씩 append를 통해 입력받아 7x7 행렬을 만들어주었다 >> 이 과정이 다소 새롭게 다가왔음)
• 7x7 행렬을 돌면서 apart[i][j]=1 && check[i][j]=False인 경우, check[i][j] = True로 값을 지정한 다음 dfs(i,j)를 통해 탐색하도록 한다.
• 이때, dfs에 들어가는 순간을 counting 해준다. (-> 단지의 수)
• dfs 함수 알고리즘
  1) dx = [-1,1,0,0] / dy=[0,0,-1,1] 로 두어 x, y 의 상하좌우를 탐색할 수 있도록 한다.
  2) for 문을 통해 4번 돌면서 x+dx, y+dy가 행렬 범위 내에 존재하고 check 내 값이 False라면, dfs(x+dx, y+dy)를 통해 탐색한다.
  3) 이때, dfs를 반복하는 횟수만큼 counting을 해준다. ( 단지 내에 있는 가구 수 )
  4) 단지 내에 있는 가구 수를 return해준다.
• dfs를 메인함수에서 돌 때 마다 반환되는 counting값을 List로 받아 sorting해준 후 출력한다.

Code (DFS)

import sys
n = int(sys.stdin.readline())
apart = []
check = [[False for _ in range(n)] for _ in range(n)]
cnt = 0
def dfs(x,y):
  global cnt
  dx = [-1, 1,0,0]
  dy = [0,0,-1,1]
  for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    if nx>=0 and nx<n and ny>=0 and ny<n:
      if check[nx][ny]==False and apart[nx][ny]==1:
        check[nx][ny] = True
        cnt+=1
        dfs(nx,ny)
        
for i in range(n):
  apart.append(list(map(int, input())))

cntList=[]
num = 0
for i in range(n):
  for j in range(n):
    if apart[i][j]==1 and check[i][j] ==False:
      check[i][j] = True
      cnt=1
      num+=1
      dfs(i,j)
      cntList.append(cnt)
print(num)
cntList.sort()
for c in cntList:
  print(c)
        

Code(BFS)

import sys
from collections import deque
n = int(sys.stdin.readline())
apart=[]
result=[]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(a,b,check):
  num = 1
  check[a][b] = 1
  q = deque()
  q.append((a,b))
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx,ny = x+dx[i], y+dy[i]
      if nx>=0 and nx<n and ny>=0 and ny<n:
        if apart[nx][ny]==1 and check[nx][ny]==0:
          q.append((nx,ny))
          check[nx][ny]= 1
          num+=1
  result.append(num)
if __name__=='__main__':
  cnt =0
  for _ in range(n):
    apart.append(list(map(int, sys.stdin.readline().rstrip('\n'))))
  check=[[0 for _ in range(n)] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if apart[i][j]==1 and check[i][j]==0:
        cnt+=1
        bfs(i,j,check)
  print(cnt)
  result.sort()
  for r in result:
    print(r)

++) 2/9 다시 풀어봄

• 주어진 조건을 꼼꼼하게 파악하자(ex.오름차순 정렬)