해결 과정
cabbages를 하나씩 pop 하면서 BFS를 돌렸다.
나의 풀이
from collections import deque
T = int(input())
for i in range(T):
M, N, K = map(int, input().split())
cabbages = []
for i in range(K):
a, b = map(int, input().split())
cabbages.append((a, b))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
count = 0
while cabbages:
queue.append(cabbages.pop())
while queue:
cur = queue.popleft()
for i in range(4):
x = cur[0] + dx[i]
y = cur[1] + dy[i]
if (x, y) in cabbages:
queue.append((x, y))
cabbages.remove((x, y))
count += 1
print(count)
다른 풀이
이중 for 문으로 (x, y)를 모두 돌면서 DFS/BFS를 사용하는 풀이들. 방문 여부는 1 -> 0 으로 바꿔주면서 풀이.
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
T = int(input())
def search(x,y):
if x < 0 or x >= M or y < 0 or y >= N:
return
if graph[x][y] == 0:
return
graph[x][y] = 0 # 탐색한 배추는 0으로 갱신
# 동서남북 탐색
search(x+1,y)
search(x,y+1)
search(x-1,y)
search(x,y-1)
for _ in range(T):
N, M, K = map(int, input().split()) # 가로길이, 세로길이, 배추 수
graph = [[0] * N for _ in range(M)]
result = 0 # 지렁이 수
# 그래프 생성
for _ in range(K): # 배추 수 만큼 반복
a,b = map(int,input().split())
graph[b][a] = 1 # 배추 위치 표기
# dfs
for i in range(M):
for j in range(N):
if graph[i][j] == 1: # 배추가 존재하는 경우
search(i,j) # 인접 배추 탐색
result += 1 # search가 종료하면, 지렁이 수 추가
print(result)
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
t = int(input())
def bfs(graph, a, b):
queue = deque()
queue.append((a,b))
graph[a][b] = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if nx < 0 or nx >=n or ny < 0 or ny >= m:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = 0
queue.append((nx, ny))
return
for i in range(t):
cnt = 0
n, m, k = map(int,input().split())
graph = [[0]*m for _ in range(n)]
for j in range(k):
x, y = map(int, input().split())
graph[x][y] = 1
for a in range(n):
for b in range(m):
if graph[a][b] == 1:
bfs(graph, a, b)
cnt += 1
print(cnt)
IDEA
'Coding Test > 문제 풀이' 카테고리의 다른 글
[문제 풀이] 백준 1389 (0) | 2022.04.04 |
---|---|
[문제 풀이] 백준 1074 (0) | 2022.03.29 |
[문제 풀이] 실패율 (0) | 2022.03.25 |
[문제 풀이] 백준 10825 (0) | 2022.03.25 |
[문제 풀이] 백준 1446 (0) | 2022.03.25 |