[python3] 이것이 취업을 위한 코딩 테스트다 - 음료수 얼려 먹기 (ch5. DFS/BFS)

참고) 이것이 취업을 위한 코딩테스트다 with 파이썬 책을 기반으로 작성된 문제와 코드입니다. 
따라서 문제는 자세하게 적지 않고, 간단한 설명과 제 코드만 올리겠습니다.

 

실전문제(1) 음료수 얼려먹기

- N x M 크기의 얼음틀
- 구멍칸 0 칸막이칸 1
- 구멍이 뚫려있는 부분끼리 상하좌우로 붙어있는 경우 서로 연결되어 있다고 간주
- 얼음틀이 주어졌을 때, 생성되는 아이스크림의 총 갯수를 구하는 프로그램 작성

##### 입력조건
- 첫쨋줄에 얼음틀의 세로 N 가로 M 주어짐
- 1<= N, M <= 1000
- 두번째 줄 부터 N+1줄까지 얼음틀의 형태 주어짐
- 구멍이 뚫려있는 부분은 0 그렇지않은 부분 1

 

<문제 풀이 >

1. DFS 를 활용하여 문제를 푼다. (DFS/BFS 어떤 알고리즘을 활용해야하는지 아직 감이 안온다.)
2 . 처음 (0,0)부터 방문을 시작
3. (0,0) 상하좌우에 구멍이뚫려있는(0) 곳이 있는지 확인한다.
4. 만약 구멍이 뚫려 있다면 뚫려있는 곳을 1로 바꿔준다. (바꿔주지 않으면 다음에 또 갯수를 세기 떄문이다. 그리고 어쨋든 (0,0)과 연결된 곳이기 때문에 1번만 세어주어야 하기 때문이다. 즉, (0,0)과 인접한 모든 0은 1로 바꿔주는 것이다~)
5. 최종 값으로 True를 출력할 것이다. 나중에 True인 것만 카운트 하기 위해서다.

 

<내가 푼 코드 및 답안 예시 코드>

DFS 재귀함수를 어떻게 활용해야할지 몰라서 답안을 참고하며 풀었다. 그래도 시간이 오래걸렸다. 너무 어렵다.. 많은 문제를 접해보면서 감을 잡는게 중요한 것 같다.

#입력받는 코드
n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
# 재귀를 활용한 dfs 로 구현하는것이 tip
def dfs(x, y):
    # 들어오는 수 xy가 범위를 벗어나면 그냥 바로 false처리
    if x >= n or y >= m or x < 0 or y < 0:
        return False
    
    #방문노드 확인
    if graph[x][y] == 0:
        #방문하지 않았다면 방문처리
        graph[x][y] = 1
        #그다음 상하좌우를 살펴보고 상하좌우가 0이면 1로 또 바꾸어주면서 방문해야해
        # 이때 다시 함수를 작성하지 말고 재귀를 활용하자
        dfs(x-1, y) #상
        dfs(x+1, y) #하
        dfs(x, y-1) #좌
        dfs(x, y+1) #우
        return True # 0이니까 true로 반환해준다
    return False #0이 아니니까False로...

# 모든 노드를 반복문으로 확인해보기
result = 0
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            result += 1
            
print(result)

• 출력

첫쨋줄 : N M 입력받음
둘쨋줄 부터 N+1번쨋 줄까지는 1과 0에 대한 정보를 입력받는다
셋쨋줄 : 최종 출력값이다

 

 

아 ... 어렵다 ㅠㅠㅠ 문제를 많이 풀어보면서 익숙해져야겠다.