글 읽기 - 왜 틀렸습니다라고 뜰까요ㅜㅜㅜ

hjg223 2년 전 0

컴파일, 예제 출력은 제대로 됩니다. 코딩 배운지 1개월밖에 안된 코린이라 어디가 잘못된지 정말 모르겠습니다,,ㅠㅡㅜ

from collections import deque
hdx = [-2, -2, 2, 2, -1, -1, 1, 1]
hdy = [-1, 1, -1, 1, -2, 2, -2, 2]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y, k): #k번 카운트 
    kcnt = 0
    cnt = -1
    q.append([x, y])
    while q:
        cnt += 1
        x, y = q.popleft()
        if x == h - 1 and y == w - 1:
            return visited[x][y]
        for t in range(2):
            if t == 0:
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and visited[nx][ny] == 0:
                        q.append([nx, ny])
                        visited[nx][ny] = visited[x][y] + 1
            if t == 1 and kcnt < k:
                for i in range(8):
                    nx = x + hdx[i]
                    ny = y + hdy[i]
                    if 0 <= nx < h and 0 <= ny < w and visited[nx][ny] == 0:
                        q.append([nx, ny])
                        visited[nx][ny] = visited[x][y] + 1
                        kcnt += 1
    return -1
            
visited = []
q = deque()
k = int(input())
w, h = map(int, input().split())
for i in range(h):
    visited.append(list(map(int, input().split())))
print(bfs(0, 0, k))

visited[x][y] = 0 인 경우에 nx ny에 대해서 큐에 push를 하는데(즉, 해당지점에 말이동 갯수에 따른 방문없이 한번만 방문), 이렇게 하면 x,y에 대해서 말이동없이 가는경우 말이동 1~k번 이동해서 가는 모든 경우에 대해서 탐색을 못합니다. 왠만하면 말이동해서 가는경우가 dist값이 작으니, 초기에 말이동하면서 도달하는 dist값만 들어가게 될꺼같네요. 쉽게 말해서 탐색해야하는 부분을 방문을 안하고 코드가 돌아갑니다.

반례로, 임의의 x, y에대해서 말이동없이 도착한후에 말이동을 해서 목적지에 도착해야 답이나오는 경우에 대해서 답을 구할수 없을꺼같네요.

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

문제

문제

출처

ICPC

왜 틀렸습니다라고 뜰까요ㅜㅜㅜ

hjg223 2년 전 0

aksndk123 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말