문제 : https://www.acmicpc.net/problem/1012
BFS 문제다.
맵에서 섬이 몇개냐, 단지가 몇개냐 하는 문제는 bfs로 풀 수 있는것 같다.
왜 ~인 것 같다 면 난 이런 코딩테스트 문제들을 많이 안풀어봤고 실력도 솔직히 별로 없기 때문이다.
========이 아래로 뇌피셜========
이런 문제들은 bfs를 모든 맵에서 시작해보는 것으로 한다.
그리고 방문 확인용 배열 v를 만든다. 이 배열은 문제 내 모든 bfs 를 사용할때 공통적으로 사용된다.
그 후, deque를 통한 bfs를 돌리는데, v 를 통해 방문을 확인하고, 맵에서 (i,j) 지점이 섬/단지/배추 등등 우리가 필요한 곳인지 확인하는 작업이 필요하다. 아니면 continue를 통해 (i,j) 점에서 bfs는 돌리지 않는다.
그리고 탐색을 하고, 그 다음 단지갯수/섬갯수/배추 갯수 등등 (이 문제에서는 ret) 을 +1 해준다.
import sys
from collections import deque
t = int(input())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for _ in range(t):
m, n, k = [int(i) for i in sys.stdin.readline().split()]
d = [[0]*m for _ in range(n)]
for _ in range(k):
ax, ay = [int(i) for i in sys.stdin.readline().split()]
d[ay][ax] = 1
v = [[False]*m for _ in range(n)]
ret = 0
for i in range(n):
for j in range(m):
q = deque()
if v[i][j] == True or d[i][j] == 0:
continue
v[i][j] = ret
q.append((i, j))
while q:
y, x = q.popleft()
v[y][x] = True
for a in range(4):
cy, cx = y+dy[a], x+dx[a]
if 0 <= cy < n and 0 <= cx < m:
if v[cy][cx] == False and d[cy][cx] == 1:
q.append((cy, cx))
v[cy][cx] = True
ret = ret + 1
print(ret)
'취준 > 백준' 카테고리의 다른 글
[백준][Python][7562][BFS] 나이트의 이동 (0) | 2020.04.30 |
---|---|
[백준][Python][2667][BFS] 단지번호붙이기 (0) | 2020.04.29 |
[백준][Python][15970][구현] 화살표 그리기 (0) | 2020.04.12 |
[백준][Python][17609][구현] 회문 (0) | 2020.04.10 |
[백준][Python][2225][DP] 합분해 (0) | 2020.04.09 |