[Python] 백준 2178번 - 미로 탐색

문제 https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

미로 탐색 학교 수업 때 과제로 풀었었는데 그래서.. 그냥 그때 푼 코드 거의 참고했다..

bfs 너무 어렵다..

풀어놓은 코드 조금만 수정해서 풀면 되는데 인덱스 잘못 생각해서 자꾸 틀렸었다. 왜 틀린지 몰랐을 땐 풀기 싫어져서 잠시 내팽겨치고 있었다.

 

bfs함수

if v_row == n-1 and v_col == m-1:

이 부분에서 n-1, m-1이 아니라 n, m으로 해놨어서 입력한 값 다 돌았는데 또 돌게된 것이었다.

인덱스 계산 잘 하자.

 

 

궁금한 점..

사실 위에서 말한 if문 다음에 오는 break 대신 print(ans)나 return ans를 한 다음

 

함수 밖에서 함수 호출하고 마무리  #print(ans)

or

print(bfs함수)  #return ans

 

이런 식으로 하고 싶었는데 안 되더라고..

global ans를 선언한 후 if 문에서 break를 하고 함수 밖에서 bfs 함수 호출해서 print(ans)를 해야 하던데 이유를 잘 모르겠다.

스터디할 때 같이 얘기해봐야지.

 

import sys
from collections import deque

def bfs(v_row, v_col):
    global ans
    q = deque() #큐 구현을 위해 deque 사용
    visited[v_row][v_col] = True
    q.append((1, v_row, v_col)) #1칸, row, col
    while q:
        ans, v_row, v_col = q.popleft()
        if v_row == n-1 and v_col == m-1:
            break

        move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for row_move, col_move in move:
            row = v_row + row_move #v_row: 이동 전 값. row: 이동 후 값
            col = v_col + col_move
            if -1 < row < len(maze) and -1 < col < len(maze[0]):
                if not visited[row][col] and maze[row][col] == 1:
                    visited[row][col] = True
                    q.append((ans+1, row, col))

n, m = map(int, sys.stdin.readline().split())
maze = [0 for i in range(n)]
for i in range(n):
    maze[i] = list(map(int, sys.stdin.readline().strip()))
visited = [[False for j in range(m)] for i in range(n)]
bfs(0,0)
print(ans)

 

 

 

 

---

 

 

#220203

 

와 이제 bfs 기초 문제는 한 번에 코드 다 짜고 테케 돌려도 다 맞을 수(도) 있는 실력이 되었다.

알고리즘 공부는 하면 할수록 조금씩이라도 실력이 느는 게 느껴져서 재밌다!

 

import sys
from collections import deque
input = sys.stdin.readline

def bfs(y, x):
    q = deque()
    q.append((0, 0))
    maze[0][0] = 2
    while q:
        y, x = q.popleft()
        dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dy, dx in dxdy:
            nx = x + dx
            ny = y + dy
            if -1 < nx < m and -1 < ny < n:
                if maze[ny][nx] == 1:
                    maze[ny][nx] = maze[y][x] + 1
                    q.append((ny, nx))
    return maze[n-1][m-1] - 1

n, m = map(int, input().split())
maze = []
for _ in range(n):
    maze.append(list(map(int, input().strip())))

print(bfs(n, m))