글 읽기 - [파이썬] 대체 이건 무슨 신묘한 차이일까요....

ikarus101 3년 전 0

일단 문제는 맞혔습니다.

아래 코드를 맞았던 코드와 틀렸던 코드를 둘 다 올렸습니다.

두 코드의 차이점은

라인 33과 라인 73에서,

cnt -= 1을 한 뒤에 큐에 (cnt, nx, ny)를 넣어주느냐,

아니면 바로 큐에 (cnt-1, nx, ny)를 넣어주느냐의 차이밖에 나지 않습니다.

그리고 그 차이가 "틀렸습니다" 와 "맞았습니다"를 판가름합니다.

실제로,

5 5
00000
11101
00000
01111
00010

을 넣어보면 두 코드의 답은 다르게 나옵니다.

(틀렸습니다 코드 -> -1, 맞았습니다 코드 -> 9)

문제는,

두 개의 차이가 대체 뭔지 모르겠습니다.

cnt-1을 바로 넣어주나, cnt -= 1을 하고 cnt를 넣어주나 차이가 없지 않나요?

아무리 찍어봐도 cnt -= 1을 하고 나서도 0이 들어가는데....

이게... 대체.... 왜 그런걸까요....ㅠㅠ

# <맞았습니다 코드>

from collections import deque

dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)]
visited = [[[0] * m for _ in range(n)] for _ in range(2)]

def bfs(n, m):
    q = deque()
    q.append((1, 0, 0))
    visited[1][0][0] = 1
    
    while q:
        cnt, x, y = q.popleft()
        if x == n-1 and y == m-1:
            return visited[cnt][x][y]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if not visited[cnt][nx][ny]:
                if maze[nx][ny] == 0:
                    visited[cnt][nx][ny] = visited[cnt][x][y] + 1
                    q.append((cnt, nx, ny))
                if maze[nx][ny] == 1 and cnt == 1:
                        visited[0][nx][ny] = visited[cnt][x][y] + 1
                        q.append((cnt-1, nx, ny))
    return -1

res = bfs(n, m)
print(res)
                            
#=========================================================================
                            
# <틀렸습니다 코드>

from collections import deque

dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)]
visited = [[[0] * m for _ in range(n)] for _ in range(2)]

def bfs(n, m):
    q = deque()
    q.append((1, 0, 0))
    visited[1][0][0] = 1
    
    while q:
        cnt, x, y = q.popleft()
        if x == n-1 and y == m-1:
            return visited[cnt][x][y]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if not visited[cnt][nx][ny]:
                if maze[nx][ny] == 0:
                    visited[cnt][nx][ny] = visited[cnt][x][y] + 1
                    q.append((cnt, nx, ny))
                if maze[nx][ny] == 1 and cnt == 1:
                        visited[0][nx][ny] = visited[cnt][x][y] + 1
                        cnt -= 1
                        q.append((cnt, nx, ny))
    return -1

res = bfs(n, m)
print(res)

ikarus101 3년 전 4

질문 올리자마자 뭐가 문제인지 알았습니다.

cnt -= 1을 하면 for i in range(4) 문 안에서 cnt가 쭉 0으로 남는군요.

이런 기본적인 걸 떠올리지 못하다니,

역시 새벽의 힘은 대단합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 대체 이건 무슨 신묘한 차이일까요....

ikarus101 3년 전 0

ikarus101 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말