[Graph, BFS] 벽 부수고 이동하기 - 백준

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

처음으로 DP와 백트래킹으로 시도한 코드는 다음과 같다. 

 

from collections import defaultdict
n, m = [int(x) for x in input().split()]
maps = {}

for i in range(n) :
    ls = []
    get = input()
    for j in get :
        ls.append(int(j))
    maps[i] = ls

n -= 1; m -= 1

def search(maps, row, col, n, m, cnt, memo, visited = defaultdict(bool), breaks=1) :
    print(visited)
    visited[(row, col)] = True
    cnt += 1
    if (row, col) == (n, m) :
        return cnt
    if (row, col) in memo :
        return memo[(row, col)]

    route_1 = 100000; route_2 = 100000; route_3 = 100000; route_4 = 100000;

    a =False; b = False; c= False; d= False;

    if col != 0 :
        a = True
    if col != m :
        b = True
    if row != 0 :
        c = True
    if row != n :
        d = True

    if a :
        if not visited[(row, col-1)] and maps[row][col-1] == 0:
            route_1 = search(maps, row, col-1, n, m, cnt, memo, visited, breaks)
        if not visited[(row, col-1)] and maps[row][col-1] == 1:
            print(breaks)
            if breaks != 0 :
                #mas[row][col-1] = 0
                route_1 = search(maps,row, col-1, n, m, cnt,  memo, visited, 0)

    if b  :
        if not visited[(row, col+1)] and maps[row][col+1] == 0:
            route_2 = search(maps, row, col+1, n, m, cnt,  memo, visited, breaks)
        if not visited[(row, col+1)] and maps[row][col+1] == 1:
            if breaks != 0 :
                #mas[row][col+1] = 0
                route_2 = search(maps,row, col+1, n, m, cnt,  memo, visited, 0)

    if c  :
        if not visited[(row-1, col)] and maps[row-1][col] == 0:
            route_3 = search(maps, row-1, col, n, m, cnt, memo, visited, breaks)
        if not visited[(row-1, col)] and maps[row-1][col] == 1 :
            if breaks != 0 :
                #mas[row-1][col] = 0
                route_3 = search(maps,row-1, col, n, m, cnt, memo, visited, 0)

    if d  :
        if not visited[(row+1, col)] and maps[row+1][col] == 0:
            route_4 = search(maps, row+1, col, n, m, cnt, memo, visited, breaks)
        if not visited[(row+1, col)] and maps[row+1][col] == 1:
            if breaks != 0 :
                #mas[row+1][col] = 0
                route_4 = search(maps,row+1, col, n, m, cnt, memo, visited, 0)
                
    final_cnts = min(route_1, route_2, route_3, route_4)
    memo[(row, col)] = final_cnts
    return final_cnts

memo = {}
answer = search(maps, 0, 0, n, m, 0, memo)
if answer == 100000 :
    print(-1)
else : 
    print(answer)

 

하지만 11%에서 막힘을 확인하였다.

 

내가 구현한 알고리즘에는 다음과 같은 치명적인 오류가 있었다. 

 

방문한 노드가 업데이트가 되고 다시 돌아올 때 값이 보존되는 지 의문(백트래킹 이슈)

또한 벽을 부신 경우를 시뮬레이션하고 다시 돌아올 때 값이 보존되는 지도 의문

시간 복잡도가 매우 큼

 

일반적인 DP 알고리즘으로 문제를 푸려고 시도했지만 잘 되지 않았다.

 

이러한 경로 관련 문제는 어설픈 백트래킹과 DP가 아니라

일반적으로 BFS를 사용하므로 이를 활용한 연습을 꼭 익히자

 

유사한 BFS 문제로 다음 문제도 추후에 꼭 연습하자

https://programmers.co.kr/learn/courses/30/lessons/49189?language=python3 

코딩테스트 연습 - 가장 먼 노드

 

이러한 유형의 문제들을 어떻게 접근하는 지 연습할 필요성이 있다. 

위에 코드 짠다고 애 많이 먹었지만 그래도 많이 공부된 것 같아서 기쁘다.

 

그렇다면 본격적으로 BFS는 어떠한 논리로 풀이를 풀어가는 지 확인해보자

 

BFS 풀이

 

풀이는 다음 블로그 분의 풀이를 참고하였습니다.

https://letsbegin.tistory.com/30?category=870858 

[백준] 2206번 - 벽 부수고 이동하기 (DFS, BFS) - 결과 포함

 

BFS는 가중치가 1인 최단 경로 문제를 풀 때 많이 사용되는 알고리즘이고

그래프 탐색 시에 이중 배열을 만들어서 그래프를 구축해서

문제를 풀어나가는 알고리즘입니다.

 

여기 코드에서 공부를 해 나가야 하는 방법론은 다음과 같습니다.

 

1. BFS 구현 연습 with queue

2. 그래프 자료 구조 구현 방법론과 이동 구현

3. 최단 경로를 어떠한 방법으로 구하는 지

4. 방문한 경우와 아닌 경우를 별도의 자료 구조로 저장해 놓은 테크닉

 

다음과 같은 논리를 잘 기억해서 문제를 차분히 구축할 수 있도록 하자.

 

우선 BFS의 기본적인 구현 코드는 다음과 같다. 

def bfs(graph, start) :
    queue, visited = [start], []
    while len(queue) > 0 :
        vertex = queue.pop(0)
        if vertex not in visited :
            visited.append(vertex)
            for neighbor in graph[vertex] :
                queue.append(neighbor)
    return visited

input_graph = {'A' : ['B', 'C'],
               'B' : ['A', 'D', 'E'],
               'C' : ['A', 'F'],
               'D' : ['B'],
               'E' : ['B', 'F'],
               'F' : ['C', 'E']}

print(bfs(input_graph, 'A'))

 

bfs는 재귀를 사용하지 않고 구현에 들어갑니다.

즉 recursion으로 구현하지 않으며 그래프 문제를 푸는 방법을 알아야 합니다.

 

최종 구현 코드는 다음과 같습니다

## queue로 구현하기 위함
from collections import deque

### 그래프 자료구조 구축
n, m = [int(x) for x in input().split()]
graph = []

for i in range(n):
    graph.append([int(x) for x in input()])

### 방문한 노드는 재방문하지 않기 위함, 동시에 -> 방문 횟수 저장..!
### 노드의 수가 결국 최단 경로이므로
### 또한 벽을 부순 경우와 아닌 경우를 따로 저장!!!
visited = [ [ [0]*m for _ in range(n) ], [ [0]*m for _ in range(n) ]]

### moving을 구현하기 위한 방법론!! 이렇게도 구현할 수 있다..!
move_x = [-1, 1, 0, 0]
move_y = [0, 0, 1, -1]

def Breadth_First_Search(breaks, x, y) :
    queue = deque()
		### 처음 방문한 노드 저장
    queue.append([breaks, 0, 0])
    visited[breaks][0][0] = 1
		### BFS 구현하기 위한 방법
    while queue :
				### 다음 노드 방문
        breaks, x, y = queue.popleft()
				### 목적지 도달 -> 프로그램 종료
        if x == n-1 and y == m-1 :
            print(visited[breaks][x][y])
            return 
				### 4방향으로 탐색
        for i in range(4) :
            after_x = x + move_x[i]
            after_y = y + move_y[i]
						## boundary check
            if after_x < 0 or after_y < 0 or after_x >= n or after_y >= m :
                continue
						## 방문한 노드의 경우
            if visited[breaks][after_x][after_y] == 0 :
								## 방문할 수 있는 경우
                if graph[after_x][after_y] == 0 :
                    queue.append([breaks, after_x, after_y])
                    visited[breaks][after_x][after_y] = visited[breaks][x][y]+1
								## 벽이 있지만 뚫을 수 있는 경우
                if graph[after_x][after_y] == 1 and breaks == 1 :
                    queue.append([0, after_x, after_y])
                    visited[0][after_x][after_y] = visited[breaks][x][y] + 1
		### 정답을 못찾은 경우
    print(-1)
    return

Breadth_First_Search(1, 0, 0)

 

다음 문제는 유사한 문제들을 많이 풀어보면서 익히는 수 밖에 없다..!