[백준] 1012번 - 유기농 배추

문제 설명

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

문제 내용은 위 갈음하고 간단하게 설명만 하자면 상하좌우로 1이 이어져서 만들어진 집합이 몇개인지 찾아보라는 것이다. 즉 밭의 모든 구역에 배추를 심었으면 1이 상하좌우로 모두 이어져 있으므로 답은 1개가 될 것이고, 만약 대각선으로 배추가 심어져있으면 상하좌우에는 배추가 없으므로 배추의 총 개수가 답이 될 것이다.

 

문제 풀이

이 문제는 전형적인 DFS, BFS문제이다. 필자는 DFS로 문제를 풀이 하였으므로 DFS에 맞춰서 설명을 하겠다.

먼저 당연히 인접 리스트를 만들어야 한다. 크기는 문제에서 입력으로 주어지므로 그에 맞춰서 초기화를 하면 될 것이다.

하지만 여기서 중요한 점은 m,n으로 주어지는 밭의 크기가 있다면 인접리스트에 접근할때는 [n][m]으로 접근을 해야한다는 것이다.

그리고 나머지 코드는 다른 DFS 문제와 비슷하게 흘러가는데 대신 다른 점이 있다면 방문 여부를 저장할 리스트를 굳이 만들 필요는 없는 대신 1로 되어있던 값을 방문시 0으로 바꾸면 해당 위치는 방문을 한 것이므로 이 방식으로 대체하면 된다. 그러고 상하좌우를 검사하여 방문 하지 않은 곳이 있으면 DFS함수를 재귀적으로 불러오는 방법으로 문제를 풀면 되는 것이다.

 

코드

 

#백준 실버2 1012번 유기농 배추
def dfs(x,y):
  dx=[0,1,0,-1]
  dy=[1,0,-1,0]

  for i in range(4):
    new_x=x+dx[i]
    new_y=y+dy[i]
    if (0<=new_x<m) and (0<=new_y<n):
      if graph[new_y][new_x]==1:
        graph[new_y][new_x]=0
        dfs(new_x,new_y)
T=int(input())

for _ in range(T):
  cnt=0
  m,n,k=map(int,input().split())
  graph=[[0 for _ in range(m)] for _ in range(n)]
  for _ in range(k):
    x,y=map(int,input().split())
    graph[y][x]=1

  for i in range(m):
    for j in range(n):
      if graph[j][i]==1:
        dfs(i,j)
        cnt+=1
  print(cnt)

 

후기

이 문제를 풀때 위에서 주의했듯이 m,n의 위치를 바꾸어서 풀지 않아서 몇번 틀렸다.. 앞으로 문제 풀이시 2차원 리스트를 다룰때는 m,n의 위치를 잘 봐야할 것 같다.