[Python] 백준1926번 : 그림

💡문제

백준 1926번 문제 링크

🍀풀이

드디어 대망의 BFS문제다!
이전에 BFS 문제를 풀어본 적 있긴하지만 뭔가 어영부영 푼 기분?
근데 이번에 강의를 제대로 듣고 여러 유형에 대한 풀이법을 알고 나니까 뭔가 조금은 이해가 된 느낌이다. 물론 응용 문제를 풀게 되면 또 어리버리 할거 같긴한데....

유형에 따른 풀이법 블로그

파이썬으로 BFS 푸는 방법을 찾다가 발견한 블로그다. 코딩테스트에 많이 나오는 유형에 따른 풀이법?이 잘 정리되어있다!

다시 문제로 돌아가면 이 문제는 기본적인 BFS인 방문여부를 확인해서 그림의 개수와 가장 넓은 그림의 넓이를 구하는 문제였다.

코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

# 상하좌우
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

# 방문여부
visited = [[0] * m for _ in range(n)]

def bfs(x, y):
   visited[x][y] = 1		# 시작지점 방문여부 체크
   queue = deque()
   queue.append((x, y))	# 큐에 넣고
   num = 1
   
   while queue:			# 큐가 빌때까지
       x, y = queue.popleft()
       for i in range(4):	# 상하좌우 체크
           nx = x + dx[i]
           ny = y + dy[i]
           if 0 <= nx < n and 0 <= ny < m:	# 범위에 안넘어가면
               if graph[nx][ny] == 1 and visited[nx][ny] == 0:	# 그림이 있고 방문하지 않았으면
                   visited[nx][ny] = 1
                   queue.append((nx, ny))
                   num += 1
   return num

count = 0	# 그림의 개수
result = 0	# 가장 넓은 그림의 넓이
   
for i in range(n):
   for j in range(m):
       if graph[i][j] == 1 and visited[i][j] == 0:
           count += 1							# 처음 그림 추가
           result = max(bfs(i,j), result)		# 가장 넓은 그림의 넓이 찾기
           
print(count)
print(result)

이게 가장 기본적인 BFS 풀이인거 같다. 이제 이거를 토대로 방문여부 대신 최단경로를 구하는거면 방문여부 체크가 아닌 dist로 해서 값을 더해주는 방식으로 가는거 같다. 많이 풀어보고 외워놓자!