[SWEA] 1227 미로2 (Python) - DFS/BFS

DFS, BFS를 연습해보기 위해 미로2 문제를 두 가지 방식을 각각 적용하여 풀어보았습니다.

어떤게 더 효율적이었을까요?

---

📌 풀이

Code (DFS)

from collections import deque

def DFS(start):
    global visited
    stack = deque()
    stack.append(start)
    visited[start[0]][start[1]] = 1
    
    while stack:
        r, c = stack.pop()
        for k in range(4):
            nr = r + dr[k]
            nc = c + dc[k]
            if 0 <= nr < 100 and 0 <= nc < 100 and not visited[nr][nc] and maze[nr][nc] != 1:
                if maze[nr][nc] == 3:
                    return 1
                else:
                    stack.append([nr, nc])
                    visited[nr][nc] = 1
    return 0
  
for _ in range(10):
    tc = int(input())
    maze = [list(map(int, list(input()))) for _ in range(100)]
    visited = [[0]*100 for _ in range(100)]
    dr = [0, 0, 1, -1]
    dc = [1, -1, 0, 0]
    
    def find_start():
        for r in range(100):
            for c in range(100):
                if maze[r][c] == 2:
                    return [r, c]
    
    start = find_start()

    print(f'#{tc}', DFS(start))

 

Code (BFS)

from collections import deque

def BFS(start):
    global visited
    queue = deque()
    queue.append(start)
    visited[start[0]][start[1]] = 1
    
    while queue:
        r, c = queue.popleft()
        for k in range(4):
            nr = r + dr[k]
            nc = c + dc[k]
            
            if 0 <= nr < 100 and 0 <= nc < 100 and not visited[nr][nc] and maze[nr][nc] != 1:
                if maze[nr][nc] == 3:
                    return 1
                else:
                    queue.append([nr, nc])
                    visited[nr][nc] = 1
    return 0
  

for _ in range(10):
    tc = int(input())
    maze = [list(map(int, list(input()))) for _ in range(100)]
    visited = [[0]*100 for _ in range(100)]
    dr = [0, 0, 1, -1]
    dc = [1, -1, 0, 0]
    
    def find_start():
        for r in range(100):
            for c in range(100):
                if maze[r][c] == 2:
                    return [r, c]
    
    start = find_start()

    print(f'#{tc}', BFS(start))

 

Solution

1. 미로 배열을 받고, 같은 크기의 방문 리스트 배열 만들기

 

2. 현 위치에서 상하좌우를 탐색하기 위한 델타 값 설정하기

 

3. 시작 지점 좌표 찾기 (2로 표시된 칸 찾기)

 

4. 시작 지점 좌표를 DFS/BFS 함수에 파라미터로 주기

 

5. DFS/BFS 수행

• DFS
  1. 빈 스택 생성
  2. 스택에 시작 지점 좌표 넣기
  3. 시작 지점 방문 표시
  4. 스택에 요소가 없어질 때까지 while문 반복
  5. while문으로 들어오면, 스택에서 top에 있는 요소 pop
  6. pop된 좌표의 상하좌우를 탐색
  7. 배열을 벗어나지 않으면서, 방문 표시가 되어 있지 않고, 미로의 벽이 아닌 경우, 해당 좌표를 스택에 넣고 방문 표시 (만약 해당 위치가 도착 지점이라면 그 즉시 도달 가능하다는 표시인 1 반환)
  8. 스택에 요소가 다 없어질 때까지 도착 지점에 도달하지 못했다면, 도달할 수 없다는 표시인 0 반환
• BFS
  1. 빈 큐 생성
  2. 큐에 시작 지점 좌표 enqueue
  3. 시작 지점 방문 표시
  4. 큐에 요소가 없어질 때까지 while문 반복
  5. while문으로 들어오면, 큐에서 요소 dequeue
  6. dequeue된 좌표의 상하좌우를 탐색
  7. 배열을 벗어나지 않으면서, 방문 표시가 되어 있지 않고, 미로의 벽이 아닌 경우, 해당 좌표를 큐에 넣고 방문 표시 (만약 해당 위치가 도착 지점이라면 그 즉시 도달 가능하다는 표시인 1 반환)
  8. 큐에 요소가 다 없어질 때까지 도착 지점에 도달하지 못했다면, 도달할 수 없다는 표시인 0 반환

---

깨달은 점

 

두 가지 다 제출한 결과, DFS가 꽤나 유의미하게 빠르다는 사실을 알 수 있었습니다.

왜 더 빠를까요?

 

제가 생각한 바로는, 이 문제가 특정 위치에 도달할 수 있는지 여부를 알아보는 문제였기 때문입니다.

왜 이 문제에 한해서 DFS가 더 효율적인지 알아보기 위해, 각각의 특징을 한번 정리해보죠!

 

 

• DFS
  • 특징: DFS는 한 경로를 끝까지 탐색한 후에 다른 경로를 탐색하는 방식입니다. 따라서 특정 노드에 도달할 수 있는지 여부를 빠르게 확인할 수 있습니다.
  • 효율성: 그래프의 깊이가 깊고 목표 지점이 상대적으로 깊은 위치에 있을 때 DFS가 더 효율적일 수 있습니다. 하지만 그래프가 무한히 깊거나 매우 깊다면, DFS는 무한 루프에 빠질 수 있으므로 비효율적일 수 있습니다.
• BFS
  • 특징: BFS는 현재 노드와 연결된 모든 노드를 먼저 탐색한 후에 다음 깊이의 노드를 탐색합니다. 따라서 가까운 노드부터 차례대로 탐색하게 됩니다.
  • 효율성: 목표 지점이 시작점과 가까운 위치에 있을 때 BFS가 더 효율적입니다. 또한, BFS는 항상 최단 경로를 보장하기 때문에, 최단 경로를 찾는 문제에서는 BFS가 적합합니다.

이 문제는 100*100 크기의 배열에서 도착지를 찾는 것이었기 때문에 상대적으로 그래프의 깊이가 깊다고 볼 수 있습니다.

(목표 지점과 시작점이 멀리 있을 가능성이 높다는 뜻)

 

이러한 이유 때문에, DFS가 더 빨랐던 것 같습니다!

 

이 문제를 통해 깨달은 점!

BFS는 최단 경로 찾기 문제, 영역 구하기 문제에 적합하고, DFS는 도달 여부를 찾는 문제에 적합하다!