개발자 블로그
1012번 유기농 배추 본문
나의 풀이
from collections import deque
def bfs(graph, start_node):
if not graph[start_node[0]][start_node[1]]:
return False
q = deque()
q.append(start_node)
graph[start_node[0]][start_node[1]] = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while q:
current_y, current_x = q.popleft()
for i in range(4):
nx = current_x + dx[i]
ny = current_y + dy[i]
if 0 <= ny < len(graph) and 0 <= nx < len(graph[0]) and graph[ny][nx]:
graph[ny][nx] = 0
q.append((ny,nx))
return True
t = int(input())
for _ in range(t):
m, n, cabbage_num = map(int, input().split())
xy_points_list = []
for _ in range(cabbage_num):
x, y = map(int, input().split())
xy_points_list.append((x,y))
graph = [[0]*n for _ in range(m)]
for i in range(m):
for j in range(n):
if (i,j) in xy_points_list:
graph[i][j] = 1
cnt = 0
for i in range(len(graph)):
for j in range(len(graph[0])):
result = bfs(graph, (i,j))
if result:
cnt += 1
print(cnt)
섬의 갯수를 구하는 문제와 같다. 테스트 케이스 갯수가 주어지고 행렬과 배추의 갯수에 따라 각 구간의 갯수를 구하면 되는 문제이다.
주어지는 입력값이 배추의 위치 x,y점으로 하나 씩 주어진다. 위치에 대한 정보 리스트에 따로 저장해두고, 행렬 그래프에 각 위치에 1로 주어진 그래프로 만들어 준다.
만들어둔 bfs함수는 모든 점들을 돌아보면서 방문한 위치는 0으로 바꿔주며 그래프를 업데이트 시켜준다. 해당 그래프에 0인값에는 false로 각 구간이 0으로 바뀌는 곳에 방문할 때는 카운트가 올라간다.
'알고리즘 > 백준' 카테고리의 다른 글
2468번 안전 영역 (0) | 2022.07.24 |
---|---|
7576번 토마토 (0) | 2022.07.21 |
2667번 단지번호붙이기 (0) | 2022.07.17 |
1406번 에디터 (0) | 2022.07.05 |
2750번: 수정렬하기2 (0) | 2022.07.04 |