단지번호붙이기 [백준 2667] - python

import sys 
input = sys.stdin.readline

def BOJ2667() :
  global graph 
  global N
  
  direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

  def dfs(x, y, type) :
    stack = []
    stack.append([x, y])
    count = 1

    while stack :
      curr_x, curr_y = stack.pop()

      for dir in direction :
        dir_x, dir_y = dir
        next_x = dir_x + curr_x
        next_y = dir_y + curr_y
        if 0 <= next_x < N and 0 <= next_y < N and visited[next_x][next_y] == False and graph[next_x][next_y] == '1':
          visited[next_x][next_y] = type
          count += 1
          stack.append([next_x, next_y])
    return count

  N = int(input())
  graph = []
  for _ in range(N) :
    graph.append(list(input().rstrip()))

  visited = [[False for _ in range(N)] for _ in range(N)]

  answer = 0
  temp = {}
  for x in range(N) :
    for y in range(N) :
      if graph[x][y] == '1' and visited[x][y] == False :
        answer += 1
        visited[x][y] = answer
        temp[answer] = dfs(x, y, answer)

  print(answer)
  for i in sorted(temp.values()):
    print(i)

BOJ2667()

 

접근 방법 :

1. dfs를 이용해 풀었다. dfs의 개념을 숙지하고 있다면 어렵지 않게 풀수 있다.

2. x와 y의 전체 범위를 탐색하면서 집이 있다면 dfs 탐색을 실행해서 집에 연결된 모든 집에 단지 번호를 붙인다.

3. 관리하는 배열 하나를 생성해서 인덱스에 맞춰 count값을 넣어주었다.

 

 

 

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

2667번: 단지번호붙이기