[BOJ][Python] 2667번 - 단지번호붙이기[DFS/BFS - 실버 1티어]

알고리즘 태그

[DFS/DFS 탐색]

태그 설명

BFS - 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
DFS - 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 해당 노드의 끝까지 탐색하고 목표 노드에 도달하면 멈추고 아니면 그 다음 노드의 자식노드들을 또 끝까지 탐색하는 방식의 탐색법

 

DFS, BFS 비교

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

문제

백준 문제 - 단지번호붙이기

링크: 단지번호붙이기

문제설명

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

예제 입력

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력

3
7
8
9

 

탐색문제가 나오면 앞으로는 DFS/BFS 2가지 방식 모두로 풀어볼 예정이다. 알고리즘의 가장 핵심(?)이기도 하고 가장 기초적인 부분이라고 판단되어서 항상 2가지 방식으로 풀어보는 연습을 해야겠다.🤗

📃 소스코드 및 설명(DFS)

N = int(input())

# N x N 방문 유무 확인 행렬 생성
visited = [[False] * N for _ in range(N)]
# N줄 만큼 입력
graph = [list(map(int, input().strip())) for _ in range(N)]
# 상, 하, 좌, 우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

each = 0
result = []

def dfs(x, y):
    global each
    # 범위 벗어나면 중단
    if x < 0 or x >= N or y < 0 or y >= N:
        return False
      
    # 범위 안에 있는데, 방문을 안했고, 값이 1이다면 단지로 판단!
    if visited[x][y] == False and graph[x][y] == 1:
      # 조건식이 통과되면 집으로 판단하고, count UP!!
      each += 1
      # 방문으로 표시
      visited[x][y] = True
      
      # 해당 번호부터 재귀로 상,하,좌,우 탐색
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        dfs(nx, ny)
        
      return True
    return False

# x
for x in range(N):
  # y
  for y in range(N):
    if dfs(x, y) == True:
      result.append(each)
      each = 0

print(len(result))
result.sort()
for i in result:
  print(i)

📃 소스코드 및 설명(BFS)

from collections import deque
# N, M = map(int,input().split())
N = int(input())

# N x N 방문 유무 확인 행렬 생성
visited = [[False] * N for _ in range(N)]
# N줄 만큼 입력
graph = [list(map(int, input().strip())) for _ in range(N)]
# 상, 하, 좌, 우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

each = 0
result = []

def bfs(x, y):
  # 첫번째 들어온 좌표는 집이므로 1로 잡아준다.
  count = 1
  queue = deque()
  queue.append([x, y])  
  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
    # 범위 안에 있는데, 방문을 안했고, 값이 1이다면 집으로 판단!
      if 0<=nx<N and 0<=ny<N:      
        if visited[nx][ny] == False and graph[nx][ny] == 1:
          count += 1
          visited[nx][ny] = True
          queue.append([nx, ny])
  return count
        

# 열
for x in range(N):
  # 행
  for y in range(N):
    if graph[x][y] == 1 and visited[x][y] == False: 
      visited[x][y] = True
      pic = bfs(x,y)
      result.append(pic)
      
print(len(result))
result.sort()
for i in result:
  print(i)