[이것이 코딩테스트다] 음료수 얼려 먹기(Python/DFS)

문제

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

 

---

​

입력 조건

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

출력 조건

한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

---

입력 예시                                                               출력 예시

4 5                                                                        3

00110

00011

11111

00000   

---

해결

좌표에도 dfs를 많이 쓴다는 것을 보고 dx,dy를 이용한 좌표이동과 dfs를 결합해보았다.

처음 불린 dfs만 cnt를 하고 싶어서 flag를 넣었다.

처음 dfs가 불릴 때마다 flag를 false로 초기화하고 false라면 cnt가 되도록.

import sys
imput = sys.stdin.readline

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

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

#띄어쓰기 없는 2차원 배열 입력받기
arr = [list(map(int,input())) for _ in range(n)]

visited = [[False] * m for _ in range(n)]
global cnt
cnt = 0

global flag 
flag = False
def dfs(arr,x,y,visited):
    global flag
    global cnt

    if not flag:
        flag = True
        cnt +=1

    visited[x][y] = True
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx <0 or ny <0 or nx >= n or ny>= m:
            continue
        else:
            if not visited[nx][ny] and not arr[nx][ny]: 
                dfs(arr,nx,ny,visited)

#처음 dfs가 불렸을 때만 cnt++되게 어떻게 할까?
    
for i in range(n):
    for j in range(m):
        if not arr[i][j] and not visited[i][j]:
            flag = False
            dfs(arr,i,j,visited)


print(cnt)

결과적으론 성공이었다. 하지만 뭐든 flag를 넣어보려고 하는 생각이 되게 안좋은 거같음........

global 설정도 해줘야하고 맞는 지 검사하기도 까다롭다....ㅍㅍ

실제로 정답을 보니 flag없이 return boolean을 해줌.

---

참고용 책 해답

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 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 - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)
        return True
    return False

result = 0
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            result += 1
print(result)

아하 이렇게 하면 한번만 카운트 되겠구나..................................!

---

+)어려웠던점

띄어쓰기 없는 2차원 배열 입력 받기 (입출력 공부 분명 했는데;;ㅠ)

import sys
imput = sys.stdin.readline


#띄어쓰기 없는 2차원 배열 입력받기 
arr = [list(map(int,imput().split())) for _ in range(n)]
#라인으로 입력받은 후에 int로 바꾸는 게 아니라 한글자씩 int로 바꿔서 list에 넣어야함 .......

평소 imput을 만들어서 사용하곤 하는데 이렇게 되면 전체를 입력 받은 후 Int로 변환하기 때문에

00100 => 100 이렇게 저장된다 그리고 한 글자씩 저장도 안됨.......

그럼 어떻게?

arr = [list(map(int,input())) for _ in range(n)]

그냥 input으로 입력 받으면 한글자씩 int변환 후 리스트에 저장 가능..............ㅠㅠ