글 읽기 - 왜 틀렸는지 잘 모르겠습니다. 알려주세요ㅠㅠ

thwogjs98 2년 전 0

밑에 코드로 제출을 하면 중간에 실패합니다.

어떤 case에서 틀린건지 잘 모르겠습니다.

틀린 case 찾아주시면 정말 감사하겠습니다ㅠㅠ

from collections import deque
def bfs(x, y, break_cnt):
    queue = deque()
    queue.append((x, y, break_cnt))
    graph[x][y] = 2
    while queue:
        x, y, break_cnt = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m:
                if graph[nx][ny] == 0:
                    queue.append((nx, ny, break_cnt))
                    graph[nx][ny] = graph[x][y] + 1
                elif graph[nx][ny] == 1:
                    if break_cnt == 1:
                        queue.append((nx, ny, 0))
                        graph[nx][ny] = graph[x][y] + 1
    return graph[n-1][m-1]

graph = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, m = map(int, input().split())
for _ in range(n):
    graph.append(list(map(int, input())))
result = bfs(0, 0, 1)
if result == 0:
    print(-1)
else:
    print(result-1)

yunx2 2년 전 1

hmm...

duddnd919 2년 전 5

break_cnt로 벽을 부쉈는지 부수지 않았는지 구별하는 것까지는 좋았으나

결국 벽을 부순 후의 최종적으로 나온 결과와

벽을 부수지 않은 후의 결과를 비교해야합니다.

즉 두 값을 모두 가지고 있어야만 한다는 것이지요.

그 두 값을 모두 가지는 방법 중 하나로 graph의 축을 하나 더 만드는 것이 있습니다.

그러면 그래프가 총 3차원 배열이 되는데

graph[벽을 부순 경우인가?][y][x] 이렇게 인덱스에 의미를 넣을 수 있겠습니다.

그러니까 벽을 한 번 부수고 진행하는 경우의 세계와 (저는 BFS를 평행세계로 이해하며 코드를 짜기 때문에 이 단어선택에 대해서는 양해부탁드립니다)

벽을 부수지 않고 진행하는 경우의 세계를 모두 BFS로 돌리는 거죠.

그렇게 하면 두 세계에서의 최단 거리를 구할 수 있게 되는데

그걸 비교하면 됩니다.

thwogjs98 2년 전 1

아.. 그렇군요 어디가 문제였던건지 알았습니다.

감사합니다!!!

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

문제

문제

출처

ICPC

왜 틀렸는지 잘 모르겠습니다. 알려주세요ㅠㅠ

thwogjs98 2년 전 0

yunx2 2년 전 1

duddnd919 2년 전 5

thwogjs98 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말