DFS문제 (음료수 얼려 먹기) - 이것이 코딩 테스트다

DFS문제 (음료수 얼려 먹기) - 이것이 코딩 테스트다

 

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

 

0	0	1	1	0
0	0	0	1	1
1	1	1	1	1
0	0	0	0	0

입력 조건: 

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다.(1 <=N, M <=1,000)
• 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

 

문제의 해결 키워드는 DFS이다. 0끼리는 이어져있으므로 이어져있지 않는 곳까지 탐색을 한 뒤, count를 올려주면 된다.

 

문제는 구현방법이다. 어떻게 구현해야할까?

1. visited라는 True or False리스트를 굳이 안 사용해도 된다. 숫자가 1일 경우 False를 반환하면 되기 때문이다. 

2. dfs의 함수인자에 x와 y를 N x M 만큼 주면서 graph[x][y]가 True가 될 시에 count를 하나 올릴 것이다. graph[x][y]가 True가 되었다는 것은 dfs함수 내부에서 갈 수 있는 모든 곳을 다 다녔을 때 True가 나오기 때문이다.

 

코드는 아래와 같다.

 

n,m = map(int,input().split())

graph = []
for i in range(n):
  graph.append(list(map(int,input())))

def dfs(x,y):
  if x <= -1 or y <= -1 or x >=n or y >=m :
    return False
  if graph[x][y] == 0:
    graph[x][y] = 1
    dfs(x-1,y)
    dfs(x+1,y)
    dfs(x,y-1)
    dfs(x,y+1)
    return True
  return False
  
count =0
for i in range(n):
  for j in range(m):
    if dfs(i,j) == True:
      count += 1
      
print(count)
 

map(int, input().split())    --> 공백을 통해 입력을 받은 뒤 int로

 

list(map(int,input()))  --> list를 받는데 입력을 받은 뒤 int로

 

저 위에 dfs(x-1,y) , dfs(x+1,y), dfs(x,y-1), dfs(x,y+1)을 for k in range(4)로 해서 nx = x + dx[i], ny = y+ dy[i]를 해보았더니 되지 않았다. 조건에 문제가있는걸까? 큐에서는 저러한 식을 사용하는데 여기서는 안쓰는 이유를 잘 모르겠다.