글 읽기 - 이게 무슨 차이인지 도저히 모르겠습니다. 제발 도와주세요...

ikarus101 3년 전 0

안녕하세요, 미리 감사 인사드립니다.

~~예제 문제는 통과했으나, 33%에서 틀렸습니다가 뜹니다.~~

~~나이트 문제 같은 경우 질문이 3페이지 밖에 없어서 검색한 반례는 모두 넣어봤지만 모두 통과하였습니다...~~

~~혹시 반례 좀 알려주실 수 있을까요?~~

일단 문제 자체는 해결하였습니다.

하지만 이상한 점이....

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

보시다시피, 차이점은

cnt 변수에 chess[nx][ny] 를 담느냐, 아니면 담지 않고 바로 chess[nx][ny]로 리턴하느냐 일 뿐입니다.

cnt 변수에 담아도 예제 테케는 당연히 통과하고요, 게시판에서 검색한 반례도 다 맞았지만,

33%에서 틀렸습니다가 떴었습니다.

무엇이 잘못된 것일까요....?

# 틀린 소스 코드 !!!!!!!!!!!!!!!!!

from collections import deque

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

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

def init_chess(n, ax, ay):
    chess = [[0] * n for _ in range(n)]
    chess[ax][ay] = -1
    
    return chess

res = []        
T = int(input())
for _ in range(T):
    n = int(input())
    x, y = map(int, input().split())
    ax, ay = map(int, input().split())
    
    if x == ax and y == ay:
        res.append(0)
        continue
    
    chess = init_chess(n, ax, ay)
    res.append(bfs(x, y, n))

for i in range(len(res)):
    print(res[i])
    
#-------------------------------------------------------------

# 정답인 소스 코드!!!!!!!!!

# BOJ 7562
# knight

from collections import deque

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

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

def init_chess(n, ax, ay):
    chess = [[0] * n for _ in range(n)]
    chess[ax][ay] = -1
    
    return chess

res = []        
T = int(input())
for _ in range(T):
    n = int(input())
    x, y = map(int, input().split())
    ax, ay = map(int, input().split())
    
    if x == ax and y == ay:
        res.append(0)
        continue
    
    chess = init_chess(n, ax, ay)
    res.append(bfs(chess, x, y, n))

for i in range(len(res)):
    print(res[i])

yjwr0528 3년 전 1

위쪽 코드의 반례 하나 드릴게요.

0 0

7 7

정답은 6입니다. 위쪽 코드는 5를 출력하네요.

체스판을 보니까 맨 끝 칸이 유일하게 5번 만에 이동이 불가능한 칸이더라구요.

문제

문제

출처

ICPC

이게 무슨 차이인지 도저히 모르겠습니다. 제발 도와주세요...

ikarus101 3년 전 0

yjwr0528 3년 전 1

ikarus101 3년 전 0

yjwr0528님, 감사합니다!

체증이 내려가는 느낌입니다 ㅠㅠ

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말