[이코테] DFS, BFS - 음료수 얼려먹기

오랜만에 포스팅한다... 왜냐? DFS BFS 개념도 이해하는데 시간이 걸렸기 때문

한 번도 시도해보거나 연습해본 사고의 패턴이 아니기 때문에 (누가 일상생활에서 저렇게 생각해요;) 좀 걸렸다

잡설이 긴 이유? 그것은 이번 음료수 얼려먹기도 손도 못 대고 결국 정답을 봤기 때문이지

 

1. 내 풀이

진짜 처참해서 보여줄 수 없음... graph로 input 받는 것도 실패함

 

1-1. 풀이 도중 생각

1) 0을 기준으로 탐색하고, 종료되는 한 세트를 아이스크림 1개로 카운트하면 될 것 같다

2) 0을 기준으로 탐색하고 모든 노드에 대해서 탐색을 시작하는 것으로 짜면 될 것 같은데 그러면 아이스크림을 중복해서 세는 위험이 있지 않을까? 이것을 어떻게 처리해줄 수 있을까?

3) 방문처리를 어떻게 해줄 수 있을까? 1로 처리를 하면 되는 걸까? 1로 처리했을 때 문제에서 주어진 조건을 변형시켜버려 풀이가 꼬이는 것은 아닐까?

 

2. 정답

# 문제의 n, m 값 입력받기
n, m = map(int, input().split())

# 2차원 리스트 만들기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
print(graph)

# DFS로 특정 노드 방문 후 그와 연결되어 있는 노드들 방문하기
def dfs(x, y):
    # 2차원 리스트의 범위를 벗어나는 경우
    if x <= -1 or x>=n or y<=-1 or y>=n:
        return False
    # 아직 방문하지 않은 노드라면
    if graph[x][y] == 0:
        # 방문 처리
        # 방문 처리를 1로 해도 괜춘
        # 어짜피 우리는 0값인 것들만 탐색할 것이고, 1인 것은 false로 할 것이니까
        # 그렇게 하면 아이스크림 카운트할 때도 중복이 발생하지 않음
        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):
        if dfs(i, j) == True:
            result += 1
print(result)

 

3. 새로 공부하게 된 것 or 새삼 다시 알게 된 것

1) list() 는 안에 있는 인자를 다 분리해서 리스트로 반환해준다 ('hello' -> ['h', 'e', 'l', 'l', 'o']

2) 아직 재귀함수의 처리 방식에 대해서 온전히 알지 못하고 있다. 재귀함수가 여러 줄 있는 경우 처리가 어떻게 되는 것인지...? 다 병렬적으로 돌아가나..? (dfs(x-1,y), dfs(x,y-1), dfs(x+1,y), dfs(x,y+1) 요 부분)