[알고리즘,개념,활용] 길을 찾자!

이 글은 BFS/DFS에 대한 저의 이해를 기록한 글 입니다. 사람마다 이해하는 방법이 다를 수 있으니, 너그러운 시선으로 봐주세요! 대신, 틀린 부분이 있다면, 거침없이 지적/tackle해주세요 !

경로 찾기 문제 

• 알고리즘 문제를 풀다보면 , BFS 관련해서 자주 등장하게 되는게 , 길찾기 문제이다. 이 길찾기 문제에 대해서, 하나하나 뜯어볼 생각이다.

 

왜 BFS,DFS는 경로 찾기 문제에 쓰일까

• 당연하다. BFS, DFS는 완전 탐색 알고리즘 중, 하나이고 모든 경우의 수를 보는 알고리즘이기 때문에, 답을 못찾을 수가 없다고 말하면 알고리즘을 배우는 의미가 없으니까 , 말해주면 길찾기 문제의 Map을 그래프 관계로 나타낼 수 있고, 이 배열을 하나하나 다 순회하면서 탐색하는것보단, BFS,DFS로 쭊쭊 퍼져가면서 탐색하는게 훨씬 효율적이기 때문.

 

경로를 찾는 Map 표현하는 방법

• 보통 BFS 문제를 보면 아래와 같이 , 0과 1 혹은 , 0,*,$,# 등등 다양한 요소로 길을 진행하는데 방해하는 요소들(벽,불,물,돌 등)을 2차원맵에  표현하게 된다.

밑은 '0'은 벽이고 ,'1'은 지나갈 수 있는 통로라고 생각해보자. 그럼, 빨간선을 따라, 우리는 길을 찾아가게 될거다.

 

여기서, BFS,DFS를 쓰려고하면, 막막할 것이다. "내가 아는 BFS,DFS는 우선 인접행렬/인접리스트로 표현이 되어야만, BFS,DFS를 사용할 수 있는데.." 엄밀히 말하자면, 이건 잘못된 생각이기도 하고, 맞는 생각이기도 하다.

 

1. BFS,DFS는 완전탐색 중에 한 방법이다.

2. 세상의 모든 관계는 그래프로 나타낼 수 있다. (인간관계는 모르겠다)

 

길찾기 문제가 나오고, 2차원 맵이 나온다면, 2차원 맵의 각각 칸 = Node , 칸들 끼리의 연결관계 = Edge라고 생각하면 된다. 즉, 위의 예시에서는 (0,0) -> (1,0) -> (2,0)->  (3,0) ->  (3,1)-> (3,2) -> (2,3)->  (1,3)->  (1,4) 로 진행이 되고있다. 이렇게 나타내니까 , 마치 노드끼리, edge로 연결되어있는 그래프와 똑같이 느껴진다. 

 

BFS,DFS로 탐색하는 방법

1. 방문했던 곳은 방문하지 않음.

• chk를 boolean으로 선언해도 되고, 정수형으로 선언해서, 기록해줘도된다. boolean선언이냐, 정수형 선언이냐에 따라서, 장/단점은 있으나, 뭘로 해줘도 상관없음!

2. 범위체크는 항상 먼저 !

• 탐색을 할때, 범위를 먼저 벗어나게 되면, out of index가 발생하므로, 항상 탐색하기 전에는 범위체크가 우선적으로 진행되어야한다.

3. 상대좌표의 개념을 써서, if문의 작성을 줄이자! 

• 상,하,좌,우를 탐색 또는 , 상,하,좌,우,대각선들 (팔방)으로 탐색해야하는 경우가 있는데, 이때 상대좌표의 개념을 사용해주면 좋다. 

코드로 구현해보자. (BFS)

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)
#상대좌표 , 나는 오른쪽 -> 위쪽 -> 왼쪽 -> 아래쪽 순으로 탐색하는걸 좋아함.

def is_valid_coord(y, x):
    return 0 <= y < 100 and 0 <= x < 100

def bfs(sy, sx):  # start y, x
    chk = [[False] * 100 for _ in range(100)]
    chk[sy][sx] = True
    q = deque()
    q.append((sy, sx))
    while q:
        y, x = q.popleft()
        for k in range(4):
            ny = y + dy[k]  # next y, x
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and not chk[ny][nx]:
                chk[ny][nx] = True
                q.append((ny, nx))

코드로 구현(DFS)

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)
chk = [[False] * 100 for _ in range(100)]

def is_valid_coord(y, x):
    return 0 <= y < 100 and 0 <= x < 100

def dfs(y, x):
    for k in range(4):
        ny = y + dy[k]  # next y, x
        nx = x + dx[k]
        if is_valid_coord(ny, nx) and not chk[ny][nx]:
            chk[ny][nx] = True
            dfs(ny, nx)

chk[sy][sx] = True  # start y, x
dfs(sy, sx)