[코드트리 챌린지](6주차) BFS/네방향탈출가능여부판단하기

문제:

풀이:

넘 dfs만 푼거같아서 bfs도 풀어보았다. 자료구조시간에 큐를 이용해서 어찌저찌 한다고 했었던 기억이 희미하게 났는데 이걸 직접 구현하려니 너무 기억이 오래돼서 쉽지 않았다. 그래서 기본개념 탭으로 공부를 좀 하고 풀었다. 하도 dfs때 재귀함수만 써가지고.. 반복무능로 구현하는데 너무 낯설었다.

 

코드:

from collections import deque
n , m = map(int, input().split())
arr = [
    list(map(int, input().split()))
    for _ in range(n)
]
visited = [[False]*m for _ in range(n)]
q = deque()
def push(x, y):
    q.append((x, y))
    visited[x][y] = True
have_ways = 0

def can_go(x, y):
    if x<0 or x >= n or y<0 or y>=m: return False
    if visited[x][y]: return False
    if arr[x][y] == 0: return False
    return True

def bfs():
    global have_ways
    dxs, dys = [0, 1, -1, 0], [1, 0, 0, -1]
    while q:
        (x, y) = q.popleft()
        for dx, dy in zip(dxs, dys):
            new_x = x+dx
            new_y = y+dy
            if can_go(new_x,new_y):
                if (new_x, new_y) == (n-1, m-1): 
                    have_ways = 1
                    return
                push(new_x, new_y)
push(0, 0)
bfs()
print(have_ways)

문제링크: https://www.codetree.ai/missions/2/problems/determine-escapableness-with-4-ways?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

---

실력진단:

ㅠㅠ

또 똑같은데서 못품. backtracking 아무래도 다음주엔 여기 공부해야겠다. 거의다 풀 수 있었는데 하나만 출력되고 끝나가지고.. 원인을 못 찾아가지고.....