[이코테] 음료수 얼려 먹기 (BFS)

1. 해결 방법

"""
1. 아이디어
- 2중 for문 => int[][]
- BFS를 돌면서 +1, 생성되는 아이스크림의 개수를 구함

2. 시간복잡도
- O(V + E)
- V : m X n = 1000 X 1000 = 1000000
- E : 4V = 4 * 1000000

3. 자료구조
- 얼음 틀 2차원 배열 : int[][]
- 방문 : bool[][]
- BFS(Queue)
"""

그래프 형태이기 때문에 2차원 배열을 사용해야 한다. 마찬가지로 방문 기록을 남겨야 하기 때문에 bool 형태의 2차원 배열을 추가적으로 구현하였다.
하나의 노드(vertex)를 방문하면 그 노드와 연관되어있는 자식 노드를 추가적으로 방문하여 큐에 넣는다. 이런식으로 하나의 얼음 틀을 만들때 까지 방문하다가 연결이 끊길 때에는 반복문을 이용한 탐색을 종료시켜 하나의 얼음 틀(아이스크림) 개수를 추가시킨다.

시간복잡도는 2억개 미만이므로 구현이 가능하다.

 

 

2. 코드

입력 예제 (1)

4 5
00110
00011
11111
00000

출력 예제 (1)

3

 

 

입력 예제 (2)

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력 예제 (2)

8

 

해결 코드

from collections import deque
import sys
# input = sys.stdin.readline

# n, m 입력
n, m = map(int, input().split())
map = [list(map(int, input())) for _ in range(n)]
chk = [[False] * m for _ in range(n)]

cnt = 0

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


# bfs
def bfs(y, x):
    q = deque()
    q.append((y, x))

    while q:
        ey, ex = q.popleft()
        for k in range(4):
            ny = ey + dy[k]
            nx = ex + dx[k]
            if 0 <= ny < n and 0 <= nx < m:
                if map[ny][nx] == 0 and chk[ny][nx] == False:
                    chk[ny][nx] = True
                    q.append((ny, nx))

    return True


# main
for j in range(n):
    # print('j=',j)
    for i in range(m):
        # print('i=',i)
        if map[j][i] == 0 and chk[j][i] == False:
            cnt += 1
            # print(cnt)
            chk[j][i] = True
            bfs(j, i)

print(cnt)

입력 예제를 입력할 때,
input = sys.stdin.readline 코드를 계속 사용해서 에러가 떴었다.

입력 시, 0 1 2 3 이런식으로 숫자 사이에 공백이 있으면 위의 input 변수를 사용해서 .split() 기능을 사용하면 되지만
111222333이런식으로 공백이 없을 때에는 input변수를 사용하지말고 input()기능을 사용하면 된다.