백준 - 14716번 현수막 python 문제풀이 [Hellfer]
https://www.acmicpc.net/problem/14716
14716번: 현수막
혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라.
www.acmicpc.net
🔷 알고리즘 분류 - 그래프 이론, BFS(너비우선탐색)
난이도 - 실버 1
너비 우선 탐색(Breadth-First Search, BFS) 알고리즘은 그래프 또는 트리를 탐색하는 방법 중 하나로, 시작 노드에서 가장 가까운 노드부터 탐색하는 방법입니다.
BFS는 '레벨(level)'이 같은 노드들을 모두 탐색한 후에 다음 레벨의 노드들을 탐색하게 됩니다.
BFS는 큐(Queue) 자료구조를 이용해서 구현됩니다.
큐는 '선입선출(FIFO, First-In-First-Out)'의 특성을 가지므로, 먼저 들어간 노드가 먼저 나오게 됩니다.
이 특성을 이용하여 BFS는 시작 노드부터 가까운 노드를 먼저 탐색하는 방식을 구현하게 됩니다.
다음은 BFS 알고리즘의 기본적인 순서입니다:
1. 시작 노드를 큐에 넣고 방문 처리를 합니다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문 처리를 합니다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.
BFS는 최단 경로 문제에서 많이 사용되며, 또한 네트워크에서 가장 가까운 노드를 찾는 등의 문제에서도 사용됩니다.
이는 BFS가 시작 노드에서 가장 가까운 노드부터 탐색하기 때문입니다.
하지만 BFS는 모든 간선의 비용이 동일할 때만 최단 경로를 보장하므로, 간선의 비용이 다른 경우에는 다른 알고리즘(예: 다익스트라 알고리즘)을 사용해야 합니다.
🔶문제 풀이 - BFS(너비우선탐색)을 이용한 풀이
from collections import deque
# 8방향을 나타내는 리스트
dx = [-1, -1,-1,0,1,1,1,0]
dy = [-1,0,1,1,1,0,-1,-1,]
# BFS 함수
def bfs(x,y):
queue = deque() # 큐 생성
queue.append((x, y)) # 시작 노드를 큐에 삽입
graph[x][y] = 0 # 시작 노드를 방문했다는 표시로 0으로 변경
while queue: # 큐가 비어있지 않는 동안
x, y = queue.popleft() # 큐에서 노드를 하나 꺼냄
for i in range(8): # 8방향에 대해
nx = x + dx[i]
ny = y + dy[i]
# 그래프 범위를 벗어나면 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 0인 노드는 무시
if graph[nx][ny] == 0:
continue
# 1인 노드를 찾았다면
if graph[nx][ny] == 1:
queue.append((nx, ny)) # 큐에 삽입
graph[nx][ny] = 0 # 방문했다는 표시로 0으로 변경
# 그래프의 크기 입력 받음
n, m = map(int, input().split())
# 그래프 정보 입력 받음
graph = [list(map(int, input().split())) for _ in range(n)]
count = 0 # 글자의 개수를 저장할 변수
for i in range(n):
for j in range(m):
# 1인 노드를 찾았다면
if graph[i][j] == 1:
bfs(i, j) # BFS 실행
count += 1 # 글자의 개수 증가
print(count) # 글자의 개수 출력🔶 문제 이해하기
아래와 같은 예시를 들어보겠습니다.
8 19
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0
0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
이 입력에서 1은 글자를, 0은 글자가 아닌 부분을 나타냅니다.
대각선 방향을 포함하여 상하좌우로 연결된 1들은 같은 글자로 간주됩니다.
위의 입력을 시각화하면 다음과 같습니다.
. . . . . . . . . . . . . . . . . . .
. . . X . . . X . . . X . X X X X X .
. . X . X . . X X . . X . . . X . . .
. X . . . X . X . X . X . . . X . . .
. X X X X X . X . X . X . . . X . . .
. X . . . X . X . . X X . . . X . . .
. X . . . X . X . . . X . . . X . . .
. . . . . . . . . . . . . . . . . . .
여기서 X는 글자를. 은 글자가 아닌 부분을 나타냅니다.
대각선을 포함하여 상하좌우로 연결된 X들은 같은 글자로 간주됩니다.
이 입력에 대한 출력은 3입니다.
이는 입력된 현수막에서 글자의 개수가 3개라는 것을 의미합니다.