음료수 얼려 먹기

---

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

• 입력
  첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다.(1<=N, M<=1000)
  두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
  이때 구멍이 뚫려있는 부분이 0, 그렇지 않은 부분은 1이다.
• 출력
  한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

띄어쓰기 없는 문자열 분리

• 계속 split()을 사용하려고 하니 입력이 이상하게 들어갔음
• 그냥 input()을 받아서 list()로 묶어주면 한 글자씩 떨어지는 것을 알았음
• \n 개행 문자가 날 힘들게함 --> strip()으로 날려버림!!
• 모두 처리한 후에 int형 변환 (map()사용) --> 다시 list()로 ! 이거 좀 복잡한데 아닐수도,, 해설 보고 다시 해봐야징~><
  세상에! 그냥 input() 받아서 map()처리후 list()로 묶으면 된다네! --> 코딩 바보인가봄! 내 코딩 실력 나락:(
  세상에! 그것도 아님 나는 sys.stdin.readline을 해서 개행문자가 자꾸 뒤에 붙는다. 위의 방식처럼 input()바로 때리면 안되네! strip()해주는게 맞느걸로!

      ice.append(list(map(int,input().strip())))

나의 풀이

---

나는 BFS를 사용하여 해결하려고 queue 를 사용했다.

인접 노드를 찾아서 연결된 노드가 있는 경우 해당 bfs알고리즘을 통해 인접 노드들을 방문 표시해주었고 queue가 비면 해당 부분은 인접 노드가 더 이상 없는 것으로 판단하여 아이스크림 하나가 생성되었다는 뜻으로 count를 1 증가해주었다. 이 것을 모든 노드가 방문되었을 때까지 반복하였다.

아래의 코드 작성

'''
음료수 얼려 먹기
입력: N,M
     얼음 틀의 형태(0:구멍뚫림,1:그렇지않음)
출력: 만들 수 있는 아이스크림 개수
'''

import sys
from collections import deque

input = sys.stdin.readline

n,m = map(int,input().split())
ice = []
for i in range(n):
    ice.append(list(map(int,input().strip())))

def bfs(graph, start, visited): # bfs 쓸거임
    queue = deque()
    visited[start] = True
    queue.append(start)
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

loc = [(-1,0),(1,0),(0,-1),(0,1)] # 상하좌우 검사 용임
graph = [[] for _ in range(n*m)]
visited = [True] * (n*m)

for i in range(n): #행
    for j in range(m): #열
        # 행과 열을 돌면서 각 노드가 0일 경우 인접 노드를 찾아서  graph 에 넣어주려고 함!
        if ice[i][j] == 0:
            visited[i*m+j] = False
            for l in loc:
                if 0<= i+l[0] < n and 0 <= j+l[1] < m and ice[i+l[0]][j+l[1]] == 0:
                    graph[i*m+j].append((i+l[0])*m+j+l[1])

answer = 0
for v in range(n*m):
    if visited[v] == False:
        bfs(graph,v,visited)
        answer += 1


print(answer)

해설

---

DFS를 사용했다고라?

얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다. --> 그래프로 모델링이 가능!

0인 값이 상, 하, 좌, 우로 연결되어 있는 노드를 묶는다. 해당 묶음을 찾는 것을 DFS 알고리즘을 사용한다.

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 0 이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
3. 1~2번 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

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

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


# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x,y):
   #주어진 범위를 벗어나는 경우에는 즉시 종료
   if x <= -1 or x >= n or y <= -1 or y >= m:
       return False
   # 현재 노드를 아직 방문하지 않았다면
   if graph[x][y] == 0:
       # 해당 노드 방문 처리
       graph[x][y] = 1
       # 상, 하, 좌, 우의 위치도 모두 재귀적으로 호출
       dfs(x-1,y)
       dfs(x,y-1)
       dfs(x+1,y)
       dfs(x,y+1)
       return True
   return False


#모든 노드에 대하여 음료수 채우기
result = 0
for i in range(n):
   for j in range(m):
       # 현재 위치에서 DFS 수행
       if dfs(i,j) == True:
           result += 1
print(result)