DFS] 음료수 얼려먹기 (feat. 이코테 2021 강의 몰아보기 문제 )

이직을 위해 코딩테스트를 준비하면서 알고리즘에 대해서 공부를 다시 생각하게 되었다.

 

  1. 내가 주로 사용하는 파이썬으로 설명되어있는지,

  2. 기업의 코딩테스트에 초점이 맞춰져 있는지, ( 너무 어려운 알고리즘이나, 이론만 설명하지 않길 바랬다. )

  3. 경향 및 필요한 이론에 대해 충분한 설명과 문제풀이가 있는지,

  4. 가능하면 무료로 이용할 수 있는지,

 

이 네 가지를 중점으로 콘텐츠를 찾아보게 되었고, 유튜브에서 좋은 내용을 찾게 되어 공부를 시작하였다.

 

나동빈님의 <이코테 2021 강의 몰아보기>

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 

 

개인적으로 DFS 까지 들어본 입장으로 충분한 이론 설명, 문제풀이 등이 담겨있고 다른 언어 ( C++,Java ) 들의 문제 풀이까지 있어서

 

주언어가 다른 사람이라도 좋은 내용이 될 것 같다. 

 

오늘은 문제 중 DFS의 문제 < 음료수 얼려먹기 > 에 대한 문제 정리를 해보겠다.

 

< 문제 >

 

주어지는 N * M의 얼음 틀이 주어지고, 0은 구멍이 뚫려있어 음료수를 채울수 있고, 1은 칸막이로 막혀있다는 가정이 있다.

0이 상하좌우로 붙어있다면,  서로 연결된다고 한다. 얼음틀 모양이 주어지면, 이에 따라 만들수 있는 최대 아이스크림 수를 구해라.

 

 

< 예시 >

 

input:              output: 

3 3                  2

010

010

010

 

< 해결 아이디어 >

전형적인 DFS,BFS 문제로 특정 지점의 주변 상하좌우를 살피며 방문하지 않은 지점으로 이동 및 방문 체크를 반복한다.

한 지점에 대한 내용이 끝나면 그 지점에서 이어진 아이스크림의 영역이 만들어지고, 이 숫자들을 세주면 완료

 

< 문제풀이 >

n, m = map(int,input().split())
# map함수로 n,m을 숫자로 변환해준다.

graph = []
for i in range(n):
    graph.append(list(map(int,input())))
# 얼음틀에 대한 정보를 저장하는 코드

def dfs(x, y):
    if x<0 or x>=n or y<0 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
n, m = map(int,input().split())

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


print(graph)


# 한 지점부터 이어질 수 있는 모든 틀에 대한 상하좌우 검사 
def dfs(x, y):
    # 종단조건 1 : 방문한 지점이 틀의 범위를 넘어가지 않아야한다.
    if x<0 or x>=n or y<0 or y>=m:
        return False
    # 종단조건 2: 방문한 지점이 이미 방문했다면 검사할 필요 없음
    if graph[x][y] == 0:
        # 방문하지 않았다면, 방문한것으로 체크 후, 주변 상하좌우 DFS 탐색
        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)

# 아이스크림 수를 체크할 변수
result = 0

# 모든 지점을 돌면서 DFS수행
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            result+=1
            # 한 지점에 대한 모든 검사가 끝나면 아이스크림수를 추가

print(result)