[SWEA] 1227.미로2 - BFS

며칠간 BFS, DFS만 판 결과 ㅠㅠㅠㅠ SWEA BFS D4레벨 문제를 온전히 내 힘으로 풀기에 성공했다!! 항상 꾸역꾸역 풀어내면 테스트케이스 몇개에서 통과가 안되든, 런타임 초과든 에러가 많아 디버깅을 엄청 했었는데.. bfs를 온전히 이해하고 나니 쉽게 풀렸다!

문제

• SWEA 1227 미로2 D4
• python
• 문제링크

SW Expert Academy

나의 코드

이 문제는 16 X 16 미로가 인풋으로 주어진 문제와 똑같은 유형이지만 인풋이 100 X 100 미로로 바뀌었다. 아무래도 효율성을 통과시키는 것이 관건이었던 문제 같은데, 어떻게 하면 메모리도 최소화 시키고 런타임도 줄일지 생각해보았다.

def check(y, x):
    return 0 <= y < N and 0 <= x < N and (maze[y][x] == 0 or maze[y][x] == 3)

def bfs(y, x):
    global result
    q = []
    q.append((y, x))
    visited.append((y, x))
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while q:
        # 가장 첫 번째 좌표 뽑기
        vy, vx = q.pop(0)
        for dir in range(4):
            # 새로 움직인 좌표
            nx = vx + dx[dir]
            ny = vy + dy[dir]
            # 조건을 통과하면
            if check(ny, nx) and (ny, nx) not in visited:
                q.append((ny, nx))
                visited.append((ny, nx))
                if maze[ny][nx] == 3:
                    result = 1


for tc in range(10):
    T = int(input())
    N = 100
    maze = [list(map(int, input())) for _ in range(N)]
    start_y = 0
    start_x = 0

    for i in range(N):
        for j in range(N):
            if maze[i][j] == 2:
                start_y = i
                start_x = j
                break
    result = 0
    visited = []
    bfs(start_y, start_x)
    print("#{} {}".format(tc + 1, result))

 

다시 정리해본 BFS pseudocode

create grid 2-D array
create visited list

def bfs(x, y):
    create queue
    append(x, y) to queue
    append(x, y) to visited

    while queue exists:
        pop first (x, y) from queue
        relocate newX index
        relocate newY index
        if (newX, newY) not in visited and within the range(len(grid)) and is a path:
            append(newX, newY) to queue
            append(newX, newY) to visited
            if grid[newX][newY] == end:
                return True