[Algorithm] 백준_1261번: 알고스팟

오늘의 추가 문제는 🚀 백준 1261 알고스팟이다.

아 굉장한 실수로 인해.. 시간을 많이 잡아먹고 결국 혼자서 해결을 못하고 구글미트로 SOS을 요청했다.

테스트케이스 이해하기

최소한 벽을 부셔서 m,n에 도착해야 한다.

p.s 조금 이상한게 가로 세로를 반대로 입력해준다… 헷갈리니 조심하시길!

알고리즘

몰랐는데 deque에 튜플이랑 리스트가 들어간다고 하더라.. 난 안되길래 q두개씩 선언해서 풀었는데ㅎ..😂

1. check를 -1로 기본값을 넣어 선언하고, 시작 위치를 0으로 설정해준다.
2. x와 y를 넣어줄 queue를 선언하고 0,0을 넣어준다
3. 4방향으로 돌면서 앞으로 나갈 경우가 범위에 들어있고, 이미 방문하지 않을 경우만 방문한다.
4. 벽이 없으면 check값을 추가해주지 않고 그대로 넣어주고, 벽이 있으면 +1을 해준다.
5. 벽이 없으면 appendleft, 벽이 있으면 append해준다!
6. 마지막 위치를 프린트 해주면 해결!

SOS친 부분 🙈🙉🙊

결국 혼자 해결하지 못하고 SOS를 친 부분은 1번이었다.

check 초기화를 0으로 해놓고 방문하지 않을 경우는 0로 확인했기 때문에,

벽이 없는 경우를 구분 하지 못했던 것이다…!!!!!!

그래서 초기값을 -1로 설정하고 시작하는 부분만 0으로 설정값을 넣주고,

방문하지 않은 곳을 확인할 때는 check == -1 로 확인했다.

바로 문제없이 실행이 되었다.

이번에 얻은 교훈: 초기화 잘하자. 제대로 하자. 제발!

도움을 주신 오앵무님께 감사를 표한다 :)

정답코드

from collections import deque

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

dx=[1,0,-1,0]
dy=[0,1,0,-1]

x = deque()
y = deque()
x.append(0)
y.append(0)

while x:
    nowX = x.popleft()
    nowY = y.popleft()
    for i in range(4):
        nxtX = nowX + dx[i]
        nxtY = nowY + dy[i]
        if -1< nxtX < m and -1< nxtY<n and check[nxtX][nxtY] == -1:
            if arr[nxtX][nxtY] == 0: #벽이 없을때
                check[nxtX][nxtY] = check[nowX][nowY]
                x.appendleft(nxtX)
                y.appendleft(nxtY)

            else:
                check[nxtX][nxtY] = check[nowX][nowY]+1
                x.append(nxtX)
                y.append(nxtY)


print(check[m-1][n-1])

🚀Reference: 백준 1261 알고스팟