글 읽기 - 3차원 배열로 하는 것이 무슨 차이인지 모르겠습니다

kdh01132006 1년 전 0

도통 갈피를 못잡아서 구글링을 하고 머리를 싸메도 이유를 못찾겠어서 처음으로 질문 남깁니다.

아래에 있는 코드가 틀렸던 제 코드입니다.

해당 코드로 예제를 돌렸을때는 값이 올바르게 나오고 머리로 논리적 흐름을 생각해봤을 때도 크게 이상한 부분을 못느꼈는데

제출만 하면 틀렸다고 나옵니다.

그래서 구글링을 해서 해답을 찾아봤는데 제 코드랑 딱 한부분만 빼고는 거의 똑같은 구조였습니다.

저는 방문한 것을 나타내는 변수(crash변수)를 bfs함수 내에서 넣어서 구동했는데

정답이라고 나온 코드는 3차원 행렬을 이용해서 visited에 c변수를 넣어 구성했습니다.

그래서 저도 6번 라인을 visited = [[[0]*2 for _ in range(M)] for _ in range(N)] 로 고치고 이에 따라 나머지 visited가 들어간 라인을

3차원 행렬로 바꾸어 제출했는데 정답이라고 나왔습니다..

제 미숙한 지식으로는 행렬로 하는 것과 제 방식으로 하는것이 무슨 차이가 있는 건지 도통 잘 모르겠습니다,,

고수님의 조언 부탁드립니다

import sys
from collections import deque)

N, M = map(int, sys.stdin.readline().split()) #세로, 가로 / 행 열
graph = [] #보드판
visited = [[0 for _ in range(M)] for _ in range(N)] #보드판
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

for _ in range(N):
    graph.append(list(map(int, input()))) #input으로 받아들이면 앞에 0도 리스트로 입력된다!

visited[0][0]=1

def bfs():
    q=deque([])
    q.append([0,0,0]) #세로, 가로, crash 변수
    while q:
        x, y, c = q.popleft()
        if x==N-1 and y==M-1:
                return visited[x][y]
        for i in range(4):
            n, m = dx[i]+x, dy[i]+y
            if 0<=n<N and 0<=m<M and visited[n][m]==0: #보드를 안벗어나면서 방문 안한곳
                if graph[n][m]==1 and c==0: #만약 벽일때 안부쉈으면
                        visited[n][m]=visited[x][y]+1
                        q.append([n, m, 1])
                elif graph[n][m]==0: #벽이 아니라면 그냥 통과가능
                    visited[n][m]=visited[x][y]+1
                    q.append([n, m, c])
    return -1


print(bfs()) 

oxcarxierra 1년 전 6

저도 똑같이 2차원 배열로 visited를 짜고 왜 틀렸는지 고민하다가, 반례중에 하나를 직접 손으로 풀어보면서 그 이유를 대충 안 것 같습니다.

예를 들어, (i,j)까지 벽을 한 번도 부수지 않고 최단경로의 길이가 A, 벽을 한번 부수고 간 최단경로의 길이가 B이며 B<A인 경우,

2차원 배열 visited에는 벽을 부수고 간 최단경로 B만 저장됩니다.

그러나 (i,j)를 지난 이후에 벽을 부수는 경로를 계산할 때에는 A로 계산을 해야 하나, 저장되어있던 B로 잘못 계산이 되는 상황이 발생하게 됩니다.

정리하자면 (i,j)까지 벽을 부순 경로가 최단거리가 되어도, (n,m)까지의 최단경로는 (I,j)까지 벽을 부수지 않고 통과할 수도 있다는 것입니다.

말로 풀어 쓰니 제가 읽어도 혼란한데 아래 반례를 한번 잘 생각해보시면 될 것 같습니다.

8 8

01000100

01010100

00010100

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

문제

문제

출처

ICPC

3차원 배열로 하는 것이 무슨 차이인지 모르겠습니다

kdh01132006 1년 전 0

oxcarxierra 1년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말