BOJ(단지번호붙이기)

작성일 | In

단지번호붙이기

  • 단지번호붙이기

  • DFS와 BFS로 탐색하는 건 알겠는데, 대체 이 문제는 어떻게 풀어야 할까.
  • 내가 헤맸던 부분은 바로 1을 찾고, (그 때 인덱스가 x,y라고 한다면) 찾은 값에 대해서 DFS함수를 실행한뒤, Map[x][y]를 0으로 초기화 해주는 작업을 통해서 문제를 해결할 수 있단 것을 배웠다.
  • 따로 checked 배열을 사용하지 않았기 때문에, 초기화를 통해서 이중 for문이 돌 때, 다시 찾게되는 경우를 방지한 것이다.
import sys


def input(): return sys.stdin.readline().rstrip()


def isSafe(x, y): return 0 <= x < N and 0 <= y < N


def DFS(x, y):
    global cnt
    Map[x][y] = '0'  # 초기화
    cnt += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if isSafe(nx, ny) and Map[nx][ny] == '1':
            DFS(nx, ny)


N = int(input())
Map = [list(input()) for _ in range(N)]
result = []
dy = [1, -1, 0, 0]
dx = [0, 0, -1, 1]
for i in range(N):
    for j in range(N):
        if Map[i][j] == '1':
            cnt = 0
            DFS(i, j)
            result.append(cnt)
print(len(result))
for i in sorted(result):
    print(i)

참고자료 codeplus 참고한블로그

0%