글 읽기 - 코드 비교 부탁드립니다.(스포주의)

algorithm_beginner 3년 전 0

오답 코드의 경우에는 table의 인덱스에 숫자의 경로를 기록했습니다. 그리고 table[b]의 값을 출력하게 했습니다.

정답 코드의 경우에는 table에 기록하는 대신 큐를 이용하여 이전 경로에서 이어나가는 식으로 하여 구현했습니다.

구현하는 방식은 달라도, 처음 방문 했을 때만 처리하는 것은 동일한데, 오답 코드는 왜 틀렸는지 모르겠네요.

답변 부탁드리겠습니다.

감사합니다

# 오답 코드
import sys
from collections import deque

def D(n):
    n *= 2
    n %= 10000
    return n

def S(n):
    if n == 0: return 9999
    return n - 1

def L(n):
    return (n % 1000) * 10 + n // 1000

def R(n):
    return (n % 10) * 1000 + n // 10

def solve():
    a, b = map(int, sys.stdin.readline().rstrip().split())
    table = ['' for _ in range(10000)]
    q = deque()
    q.append(a)

    while q:
        cn = q.popleft()

        if cn == b:
            print(table[cn])
            break

        nn = D(cn)
        if table[nn] == '':
            table[nn] = table[cn] + 'D'
            q.append(nn)

        nn = S(cn)
        if table[nn] == '':
            table[nn] = table[cn] + 'S'
            q.append(nn)
        
        nn = L(cn)
        if table[nn] == '':
            table[nn] = table[cn] + 'L'
            q.append(nn)
        
        nn = R(cn)
        if table[nn] == '':
            table[nn] = table[cn] + 'R'
            q.append(nn)


tc = int(sys.stdin.readline().rstrip())

while tc:
    solve()
    tc -= 1
#.....................................

# 정답 코드
import sys
from collections import deque

def D(n):
    n *= 2
    n %= 10000
    return n

def S(n):
    if n == 0: return 9999
    return n - 1

def L(n):
    return (n % 1000) * 10 + n // 1000

def R(n):
    return (n % 10) * 1000 + n // 10

def solve():
    a, b = map(int, sys.stdin.readline().rstrip().split())
    visited = [False for _ in range(10000)]
    q = deque()
    q.append([a, ''])
    visited[a] = True

    while q:
        cn, path = q.popleft()

        if cn == b:
            print(path)
            break

        nn = D(cn)
        if not visited[nn]:
            visited[nn] = True
            q.append([nn, path+'D'])

        nn = S(cn)
        if not visited[nn]:
            visited[nn] = True
            q.append([nn, path+'S'])
        
        nn = L(cn)
        if not visited[nn]:
            visited[nn] = True
            q.append([nn, path+'L'])
        
        nn = R(cn)
        if not visited[nn]:
            visited[nn] = True
            q.append([nn, path+'R'])


tc = int(sys.stdin.readline().rstrip())

while tc:
    solve()
    tc -= 1

algorithm_beginner 3년 전 1

자문자답이지만

오답 코드의 경우 A를 q에 넣을 때, 방문 처리를 해야하는데 하지 못했습니다. 따라서 오답코드가 됐습니다.

예를 들어 A, B가 0, 1000일 때

오답 코드는 DSDDLDSLDRDDD을 출력하고 정답 코드는 SDDLDSLDRDDD 출력합니다.

사소한 것을 제대로 확인하지 못했네요.

arkingco 3년 전 0

덕분에 문제 해결했습니다 감사합니다

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

문제

문제

출처

ICPC

코드 비교 부탁드립니다.(스포주의)

algorithm_beginner 3년 전 0

algorithm_beginner 3년 전 1

arkingco 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말