글 읽기 - [Python] 두 풀이의 차이점을 모르겠습니다.

dodobow 1년 전 0

bfs를 통해 풀었습니다.

해당 칸에 뱀이나 사다리의 시작점이 있다면 그 부분을 start에 추가하고, 빈칸이라면 1 ~ 6까지 추가한 값을 추가했습니다.

그러나 7%에서 틀렸고, 주사위를 굴린 후 그 칸의 공백 여부를 조사하는 코드로 수정하니 정답 처리되었습니다.

혹시 두 풀이의 차이점을 알려주실 수 있으신가요?

감사합니다.

#틀린 코드
from collections import deque
import sys

def bfs(x):
    start = deque([[x, 0]])
    visit[x] = 1
    while len(start) != 0:
        k = start.popleft()
        space = k[0]
        num = k[1]
        if space == 100:
            return num
        if len(board[space]) != 0:
            for i in board[space]:
                start.append([i, num])
                visit[i] = 1
        else:
            for i in range(1, 7):
                if space + i <= 100:
                    if visit[space + i] == 0:
                        start.append([space + i, num + 1])
                        visit[space + i] = 1

n, m = map(int, sys.stdin.readline().rstrip().split())
board = [[] for _ in range(101)]
visit = [0 for _ in range(101)]
for _ in range(n + m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    board[a].append(b)
print(bfs(1))

#맞은 코드
from collections import deque
import sys

def bfs(x):
    start = deque([[x, 0]])
    visit[x] = 1
    while len(start) != 0:
        k = start.popleft()
        space = k[0]
        num = k[1]
        if space == 100:
            return num
        for i in range(1, 7):
            if space + i <= 100:
                if visit[space + i] == 0:
                    if len(board[space + i]) != 0:
                        if visit[board[space + i][0]] == 0:
                            start.append([board[space + i][0], num + 1])
                    else:
                        start.append([space + i, num + 1])
                        visit[space + i] = 1

n, m = map(int, sys.stdin.readline().rstrip().split())
board = [[] for _ in range(101)]
visit = [0 for _ in range(101)]
for _ in range(n + m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    board[a].append(b)
print(bfs(1))

zenith82114 1년 전 0

처음에 일단 주사위를 던져서 이동한 다음, 거기에 뱀이나 사다리가 있으면 그것까지 타는 게 1턴입니다.

위 코드 기준으로 하면 주사위 이동만 하고 멈춰 서는 경우가 생기겠네요.

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

문제

문제

출처

ICPC

[Python] 두 풀이의 차이점을 모르겠습니다.

dodobow 1년 전 0

zenith82114 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말