[코드트리 챌린지] 6주차 (10/11-10/16), BFS

거두절미하고 진단결과부터!

 

 

점수가 오르긴 올랐다

645 -> 654

그럴만한게 평가를 하는데 마지막으로 풀었던 문제가 DFS 문제였다.

근데 분명히!!! 나는 문제없이 다 풀었다고 생각했는데 제출하면 40%까지 채점이 올라갔다가 '틀렸습니다'가 떴다

분명 히든테케에서 안맞는게 있다는 거였는데, 그렇다면 내가 뭔가 조건을 단단히 놓치고 있다는 생각이 들어서 계속 다시 봤는데 오류를 찾지 못하고 시간이 지나 평가가 끝나버렸다.

그래도 해당 문제에 대한 부분 점수가 반영이 된건지 654점으로 점수가 오르긴 올랐다.

 

 

 

 

 

 

이렇게 예상했던 것과 같이 DFS 문제를 100%해결하지 못했기 때문에 저번주와 같은 결과를 얻게 되었고, 이 김에 고난도 DFS문제들도 해결해보고, 지난주에 공부를 제대로 하지 못한 BFS를 공부하는 시간을 가져보도록 하겠다.

오히려 좋아!

 

 

 

11월 19일 딱대

참고로 진단결과를 보여줄 때, 위와 같은 화면처럼 어느정도 공부하면 되는지에 대한 정보도 제공해준다.

이게 참 마음에 든다. 확실한 동기부여를 주는 느낌?

코테라는 게 공부하면서도 막연한 느낌을 많이 받는데 이렇게 정확한 숫자값으로 '37일 후 sw역량테스트 A형 통과' 이렇게 제시해주니 학습을 하고 나서의 37일 후의 내가 너무 기대된다.

 

학습

이번엔 저번주에 학습했던 DFS와 더불어서 BFS를 학습했다.

일단 BFS는 DFS와 다르게 재귀함수가 아닌 큐를 기반으로 돌아가기 때문에 큐, 덱, 그래프탐색의 BFS의 기본 개념을 먼저 학습했다.

100%의 쾌감

이렇게 다시 완전히 기본부터 학습하면서 BFS를 공부하니까 아 왜 덱을 사용하는지, BFS는 큐를 사용해서 어떻게 탐색을 하는건지 흐름을 이해할 수 있었다.

BFS도 DFS와 마찬가지로 인접행렬, 인접리스트로 pseudo 코드를 접하게 되었는데 탐색을 하는 원리(visited로 탐색여부 확인, 그래프 범위확인 등)는 DFS와 유사했기에 이해하는 게 크게 어렵진 않았다.

다만, DFS는 재귀함수로 새로 찾은 노드를 넘기지만, BFS는 새로 찾은 노드를 큐에 추가하고 해당 큐가 비어있는 상태가 되기 전까지 계속 돌아간다는 점이 차이점이다.

이 차이점을 좀 더 명확히 체감하기 위한 문제를 풀어봤다!

 

풀어본 문제

# 네 방향 탈출 가능 여부 판별하기

위 문제를 풀어봤는데, 이 문제는 사실 5주차 DFS에서 풀어본 # 두 방향 탈출 가능 여부 판별하기와 방향만 다르고 동일한 문제이다.

차이점이라고 하면 네방향(상하좌우)와 두방향(하, 우)이라는 점이다.

n * m 크기의 이차원 영역의 좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출하려고 합니다. 이동을 할 때에는 반드시 상하좌우에 인접한 칸으로만 이동할 수 있으며, 뱀이 있는 칸으로는 이동을 할 수 없습니다. 예를 들어 <그림 1>과 같이 뱀이 배치 되어 있는 경우 실선과 같은 경로로 탈출을 할 수 있습니다. 이 때 뱀에게 물리지 않고 탈출 가능한 경로가 있는지 여부를 판별하는 코드를 작성해보세요.

이 문제 또한 풀이 전략은 동일하다.

1. n*m 그리드 범위 안에 있기

2. 뱀이 없는 자리

3. 방문하지 않았던 자리

 

여기서 다른 점은 재귀 함수가 아닌 큐로 해당 좌표를 받고 큐가 비어있을 때까지 계속 도는 것이다.

 

from collections import deque

n, m = tuple(map(int, input().split()))
q = deque()

arr = [
    list(map(int, input().split()))
    for _ in range(n)
]
visited=[
    [False]*m
    for _ in range(n)
]
dxs, dys = [0,1,0,-1],[1,0,-1,0]

def in_range(x, y):
    return 0<=x and x<n and 0<=y and y<m

def can_go(x,y):
    if not in_range(x,y):
        return False
    if visited[x][y] or arr[x][y] ==0:
        return False
    return True

def push(x, y):
    visited[x][y] = True
    q.append((x,y))

def bfs():
    while q:
        x, y = q.popleft()

        for dx, dy in zip(dxs, dys):
            new_x, new_y = x + dx, y+dy

            if can_go(new_x, new_y):
                push(new_x, new_y)

push(0,0)
bfs()

if(visited[n-1][m-1]):
    print(1)
else:
    print(0)

 

👇🏻 아래 글 보고 DFS풀이와 BFS풀이를 비교해서 보는 거 추천드립니당! 👇🏻

[코드트리 챌린지] 5주차 (10/4-10/9)

 

아직은 BFS보다 DFS가 익숙한데 문제를 더 풀면서 어떤 상황에 BFS, DFS 중에 뭐가 더 효율적일지 판단하는 사고를 가지도록 노력해야겠다!!