💡문제 분석 요약
- 이 문제와 거의 유사했다. 그리고 저 문제에다가 이차원 배열을 탐색하는 nx, ny 요소만 추가하면 됐다. 이 부분은 여기 문제와 유사했다. 저 두 문제의 방법을 합치면 될 것이다 !
- 결국, 지렁이가 몇마리냐 구하는 것은 DFS/BFS가 몇번 실행되느냐를 구하면 되는 것과 같은 맥락이었다. DFS가 아직은 더 편해서 DFS로 접근해보았다. 결국 모든 노드를 방문하는 맥락에서는 두 방법 모두 사용 가능하다.
💡알고리즘 설계
- 인접행렬, 인접리스트 2가지 방법으로 풀 수 있지만 인접행렬로 풀어보았다.
💡코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(5000)
# 순서대로 상, 하, 좌, 우로 이동하는 것을 의미
dx = [0, 0, 1, -1] # x축 방향 이동
dy = [1, -1, 0, 0] # y축 방향 이동
earthworm = 0
def DFS(x, y):
# 오류가 나는 상황을 정리한 것. 위, 아래로 움직이다가 x, y의 범위 밖으로 나가는 경우를 의미함.
if x < 0 or x >= width or y < 0 or y >= height:
return False
if graph[x][y] == 1:
graph[x][y] = 0
for i in range(4): # 상하좌우 4개의 방향을 체크함
nx = x + dx[i] # 기존의 좌표에 상하좌우를 더해줌
ny = y + dy[i]
DFS(nx, ny) # 더해준 상하좌우로 다시 탐색
return True # 모든 탐색이 완료됨
return False # 탐색이 끝나긴 했는데 0을 만나서 끝남. 즉 1로 둘러싼 경계 밖을 간 것.
for _ in range(int(input())):
width, height, cabbages = map(int, input().split()) # 배추밭 가로, 배추밭 세로, 배추개수
graph = [[0] * (height) for _ in range(width)] # 배추밭 초기화
visited = [[0] * (height) for _ in range(width)]
earthworm = 0 # 지렁이
# 배추가 심어져 있는 곳 초기화
for _ in range(cabbages):
u, v = map(int, input().split())
graph[u][v] = 1
# 초기화 끝
for x in range(width):
for y in range(height):
if graph[x][y] == 1:
DFS(x, y)
earthworm += 1
print(earthworm)
💡시간복잡도
- 모든 노드를 방문하므로 O(N^2)이 소요될 것이다. (정확히는 O(N*M) )
💡 틀린 이유
- 위에서 언급한 두개의 문제를 합치는 과정 & 그래프 초기화 하는 것에서 약간 애를 먹었다.
- visited를 선언할지 말지도 고민이었는데, 어차피 graph가 1인 곳만 방문하고, 방문한 곳은 0으로 바꿔주기 때문에 상관이 없을 것으로 보였다.
- 어이없게 하나 틀렸던 것도 있는데, 그동안 항상 노드의 시작을 1~N으로 해서 그래프 초기화 범위도 range( 1~N+1 ) 라고 했는데, 이번에도 그래프 초기화를 이렇게 했다가 입력값에 0,0이 있는 것을 보고 급히 0~N으로 range를 수정하였다. 문제를 잘 읽고 풀자 !
💡 틀린 부분 수정 or 다른 풀이
import sys
input = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def BFS(x, y):
queue = [(x,y)]
graph[x][y] = 0
while queue:
x, y = queue.pop(0)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= M or ny < 0 or ny >= N:
continue
if graph[nx][ny] == 1 :
queue.append((nx,ny))
graph[nx][ny] = 0
for i in range(int(input())):
M,N,K = map(int, input().split())
graph = [[0]*(N) for _ in range(M)]
count = 0
for j in range(K):
x,y = map(int, input().split())
graph[x][y] = 1
for x in range(M):
for y in range(N):
if graph[x][y] == 1:
BFS(x, y)
count += 1
print(count)
💡 느낀점 or 기억할정보
- BFS로도 풀어보자.
- 범위를 생각없이 1~N+1로 잡았던 것을 반성하며 문제를 잘 읽고 풀자 !
반응형
'알고리즘 > 코테 스터디 (2024)' 카테고리의 다른 글
2178 미로 탐색 (3) | 2024.07.20 |
---|---|
1697 숨바꼭질 (0) | 2024.07.19 |
11724 연결 요소의 개수 (0) | 2024.07.17 |
2667 단지번호붙이기 (0) | 2024.07.16 |
1260 DFS와 BFS (0) | 2024.07.15 |