❓ Question
https://www.acmicpc.net/problem/1012
📖 Before Start
처음으로 학습한 그래프 이론 문제를 도전해보는 마음 가짐으로!
이번 문제는 참 안타깝게 풀지 못하고 답지의 힘을 빌렸으나, 결국 풀이 방식이 아닌 엉뚱한 곳에서 실수를 했다는 사실을 깨닫고선 속으로 깊은 한숨을 내쉬었던 문제였다.
처음엔 DFS 이론으로 접근했으나, 이번 해설에서는 BFS로도 풀이한 것을 추가로 작성하고자 한다.
✒️ Design Algorithm
배추가 심어진 구역을 탐색한 후에, 인접한 배추들을 전부 뽑아버린다고 생각했다.
따라서 나는 이차원 배열을 순차적으로 탐색한 후에, 배추가 심어진 구역 (1) 이 발견된다면 탐색을 통해 주변에 심어진 배추들을 전부 뽑아버리는 것 (1을 0으로 변경) 으로 생각하고 문제를 접근하였다.
아래는 필자가 문제를 풀기 전 작성한 알고리즘 설계이다.
이차원 배열로 정의된 그래프에서, 상하좌우를 탐색하여 인접한 노드를 체크한다.
- 이차원 배열을 처음부터 끝까지 이중 반복문을 통해 탐색을 시도한다.
- 만약 1이 저장된 위치를 찾았다면, 해당 위치를 기준으로 인접한 노드를 전부 탐색한다.
- 인접한 노드의 값도 1이라면, 해당 노드를 기준으로 또 다시 인접한 노드를 전부 탐색한다.
- 더 이상 탐색을 진행할 수 없다면 주변의 배추를 모두 뽑았다는 뜻이므로 변수에 1을 더한다.
💻 Making Own Code
❌ Wrong Code
import sys
sys.setrecursionlimit(10 ** 5)
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(x, y):
if graph[x][y] > 0:
for direct in direction:
nx, ny = x + direct[0], y + direct[1]
if (0 <= nx < n and 0 <= ny < m) and graph[x][y]:
graph[nx][ny] = 0
dfs(nx, ny)
t = int(sys.stdin.readline())
for _ in range(t):
m, n, k = map(int, sys.stdin.readline().split())
graph = [[0] * m for _ in range(n)]
result = 0
for _ in range(k):
i, j = map(int, sys.stdin.readline().split())
graph[i][j] = 1
for i in range(n):
for j in range(m):
if graph[i][j] > 0:
dfs(i, j)
result += 1
print(result)
시도는 좋았으나 정말 한 끗 차이 로 문제를 풀지 못했다. 씁쓸하다..
DFS를 적용한 과정도 좋았고, 입력 받은 정보를 토대로 그래프를 이차원 배열로 표현하는 것도 좋았다.
하지만 X, Y 좌표에 대응되는 값이 이차원 배열의 어느 인덱스 인지를 제대로 파악하지 못해 틀렸다.
✅ Correct Code
import sys
sys.setrecursionlimit(10 ** 5)
# 그래프가 이동할 수 있는 방향 벡터를 list에 저장한다. (y, x)
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 인접한 1을 전부 0으로 변경하는 dfs 함수를 정의한다.
# 단, 2차원 배열에서 첫 번째 인덱스는 y, 두 번째 인덱스는 x 임을 유의.
def dfs(y, x):
graph[y][x] = 0
# 현재 위치를 기준으로, 네 방향에 대한 탐색을 진행한다.
for direct in direction:
ny = y + direct[0]
nx = x + direct[1]
# 만약 인접한 노드에 1이 있다면, 이에 대한 dfs 재귀를 진행한다.
if (0 <= ny < n and 0 <= nx < m) and graph[ny][nx]:
dfs(ny, nx)
read = sys.stdin.readline
t = int(read())
for _ in range(t):
m, n, k = map(int, read().split())
graph = [[0] * m for _ in range(n)]
count = 0
for _ in range(k):
x, y = map(int, read().split())
graph[y][x] = 1
for i in range(n):
for j in range(m):
if graph[i][j]:
dfs(i, j)
count += 1
print(count)
한참을 고민하고 수정한 끝에, 정답 코드를 같이 보면서 어떤 부분이 틀렸는지를 파악해보았다.
그 결과 그래프의 X 좌표 는 이차원 배열의 두 번째 인덱스와 대응되며,
Y 좌표 는 이차원 배열의 첫 번째 인덱스와 대응된다는 사실을 깨달았다.
내가 처음으로 작성한 DFS 함수와 수정 끝에 작성한 DFS 함수의 매개변수 순서가 다르지 않은가?
하단의 반복문을 통해 i와 j를 인자로 넘길 때, 이 값이 그래프의 x, y와 어떻게 대응되는가?
위 질문의 답은 i가 그래프 y 좌표에 대응되며 j가 그래프 x 좌표에 대응되는 것이다.
따라서 그래프 내부의 값이 1인지를 파악하는 구문도 graph[y][x] 로 작성된 것이다.
그 이후에는 인접한 노드를 미리 선언해둔 방향 벡터로 구하여 재귀적으로 DFS 탐색을 진행하면 된다.
인접한 노드가 전부 0이라면, 이중 반복문에서 다음으로 1이 나오는 구간까지 반복을 진행한다.
✅ Correct Code (with BFS)
import sys
from collections import deque
# 그래프가 이동할 수 있는 방향 벡터를 list에 저장한다. (y, x)
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 인접한 1을 전부 0으로 변경하는 bfs 함수를 정의한다.
# 단, 2차원 배열에서 첫 번째 인덱스는 y, 두 번째 인덱스는 x 임을 유의.
def bfs(y, x):
queue = deque()
queue.append((y, x))
while queue:
current_loc = queue.popleft()
# 현재 위치를 기준으로 네 방향에 대한 탐색을 진행한다.
for direct in directions:
ny = current_loc[0] + direct[0]
nx = current_loc[1] + direct[1]
# 만약 인접한 노드에 1이 있다면, 이 또한 0으로 변경하고 큐에 좌표를 추가한다.
if (0 <= nx < m and 0 <= ny < n) and graph[ny][nx]:
graph[ny][nx] = 0
queue.append((ny, nx))
# readline을 활용할 수 있는 방안, 앞으로는 이렇게 작성해보자.
read = sys.stdin.readline
t = int(read())
for _ in range(t):
m, n, k = map(int, read().split())
graph = [[0] * m for _ in range(n)]
count = 0
for _ in range(k):
# x, y인 이유는 첫번째로 가로줄에 대한 좌표를 받기 때문이다.
x, y = map(int, read().split())
graph[y][x] = 1
for i in range(n):
for j in range(m):
if graph[i][j]:
graph[i][j] = 0
bfs(i, j)
count += 1
print(count)
추가적으로 최근에 학습한 BFS 탐색 알고리즘을 사용하여 해당 문제를 다시 풀어보았다.
DFS는 재귀 함수를 사용하는 탓에 실행 속도가 느리므로, BFS의 실행 속도가 조금 더 빨랐다.
이중 반복문을 통해서 모든 그래프의 노드를 순차적으로 탐색하는 방법은 동일하였으나,
BFS는 큐를 사용하여 문제를 해결하는 방식이 더 매력적이었다. (사실 재귀가 좀 어렵다)
📖 Conclusion
📒 github Code link
처음 그래프 이론을 학습하고 풀어본 문제였는데, 생각보다 고려해야 할 점이 많다.
다음에는 보다 더 꼼꼼하게 문제를 보고, 풀이 과정을 작성해야겠다.
