[알고리즘] 이코테 음료수 얼려 먹기, 미로탈출 - 파이썬

이제 코딩 테스트를 본격적으로 공부하려 한다. 원래 학기가 끝나고 준비하려 했지만 왠지 모를 불안감에 시작했다..

 

친구가 알려준 순서와 나동빈의 이코 테를 참고해서 같이 공부하려 한다. 친구가 알려준 알고리즘 공부 순서는 '백 트랙킹, DFS, BFS, 브루트 포스, 유니온 파인드 기타 자료구조(큐, 스택, 리스트)'이고 이코테에서는 백트래킹 부분이 없어서 따로 유튜브 강의를 보고 백준을 풀 생각이다.

 

 먼저, 오늘은 BFS와 DFS를 공부했고 표로 간단히 정리하면 아래와 같다.

	DFS	BFS
동작원리	스택	큐(dequeue)
구현방법	재귀 함수 이용	큐 자료구조 이용

주의할 점은 BFS문제를 풀때 dequeue를 활용한다는 점이다.

---

문제 1) 음료수 얼려먹기

# 입력받기
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, 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)

문제풀이 : 제한시간이 30분을 넘겨 답을 보면서 풀이를 익혔다. 이 문제는 구멍이 뚫려있는 부분을 0으로 막힌 부분을 1로 표시하였는데 0으로 된 부분만을 묶은 수를 구해야 했다. 처음에는 당연히 BFS풀이로 접근해야 하나 싶었지만 풀이에서는 DFS를 활용했다. 코드를 보면 0인 지점에 대해 상하좌우를 재귀적으로 탐색하여 방문했을 경우 1로 표시하고 True를 반환하게 하여 반환된 True의 수를 카운트하는 방식으로 하였다. 

---

문제 2) 미로 탈출

from collections import deque

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

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

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    #큐가 빌때까지
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            if graph[nx][ny] == 0:
                continue

            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    return graph[n-1][m-1]


print(bfs(0,0))

문제풀이 : 이 문제도 역시나 시간 초과.. 연습이 많이 필요한 것 같다. 아직 많은 문제를 풀어보진 않았지만 최소 거리를 구하는 문제는 DFS로 푸는 것 같다. 이유는 한 노드를 시작으로 가까운 노드를 방문하기 때문에 방문할 때마다 1을 더해 주고 난 뒤 마지막에 도착지점의 N, M을 출력해보면 되기 때문이다.