파이썬) 뱀과 사다리 게임 - BOJ

 

https://www.acmicpc.net/problem/16928

이 문제는 bfs처럼 보이는 구현 문제였다.

주어진 조건만 잘 살펴보면 된다.

1. 주사위를 굴려 다음 칸으로 이동한다
2. 만약 다음칸이, 즉 nx가 사다리라면 사다리를 타고 이동한다
3. nx가 뱀이라면 뱀을타고 이동한다
4. 출발지점과 도착지점엔 뱀과 사다리가 없다

 

from collections import deque

n, m = map(int, input().split())

ladder = []
snake = []

for _ in range(n):
    a, b = map(int, input().split())
    ladder.append([100-a, 100-b])

for _ in range(m):
    a, b = map(int, input().split())
    snake.append([100-a, 100-b])

arr = [[False for _ in range(10)] for _ in range(10)]

result = 9999999999999999999


def bfs():
    q = deque()
    q.append((9, 9, 0))
    arr[9][9] = True

    while q:
        x, y, cnt = q.popleft()

        if x == 0 and y == 0:
            # 골인지점
            print(cnt)
            return

        is_ladder = False

        for l in range(len(ladder)):
            if ladder[l][0] == int(str(x) + str(y)):

                # 사다리를 만낫다면
                new_position = str(ladder[l][1])
                if len(new_position) == 1:
                    new_position = '0' + new_position
                q.append((new_position[0], new_position[1], cnt))
                arr[int(new_position[0])][int(new_position[1])] = True
                is_ladder = True
        if is_ladder == True:
            continue

        is_snake = False

        for s in range(len(snake)):
            # 뱀을 만나면
            if snake[s][0] == int(str(x) + str(y)):
                is_snake = True

        if is_snake == True:
            continue

        for i in range(1, 7):
            now = int(str(x) + str(y))
            now -= i

            if now < 0:
                # 맵을 벗어나면
                continue

            now = str(now)

            if len(now) == 1:
                now = '0' + now

            # for s in range(len(snake)):
            #     # 뱀을 만나면
            #     if snake[s][0] == int(str(x) + str(y)):
            #         is_snake = True

            # if is_snake == True:
            #     continue

            nx = int(now[0])
            ny = int(now[1])

            if arr[nx][ny] == True:
                continue

            arr[nx][ny] = True
            q.append((nx, ny, cnt+1))


bfs()

처음 작성한 코드이다.

이차원배열로 작성했고 인덱스 9,9부터 시작해 0,0으로 가는만큼 snake와 ladder또한 위치를 100에서 빼주었다.

하지만 제출 결과 30퍼 쯤에서 실패가 나왔다.

그래서 곰곰히 생각해보았다.

그러다 문득 다음 위치를 string으로 표현한 부분이 눈에 띄었다.

해당 부분을 str로 처리한 이유는 이차원 배열이기 때문이다. 그런데 굳이 이차원 배열을 쓸 필요가 있을까?

from collections import deque


n, m = map(int, input().split())

ladder = []
snake = []

for _ in range(n):
    a, b = map(int, input().split())
    ladder.append([a, b])

for _ in range(m):
    a, b = map(int, input().split())
    snake.append([a, b])

arr = [0] * 101
visit = [False] * 101


q = deque()

q.append((1))

while q:
    x = q.popleft()

    if x == 100:
        # 탈출 조건
        print(arr[x])
        break

    for i in range(1, 7):
        # 주사위 굴리기
        nx = x + i

        if nx > 100:
            # 범위를 벗어나면
            continue
        if visit[nx] == True:
            # 방문 확인
            continue

        for l in range(len(ladder)):
            # 사다리 확인
            if ladder[l][0] == nx:
                nx = ladder[l][1]

        is_snake = False

        for s in range(len(snake)):
            # 뱀 확인
            if snake[s][0] == nx:
                nx = snake[s][1]

        if is_snake:
            continue
        if visit[nx] == True:
            # 사다리에 올라 탄경우 다시 방문 확인
            continue
        visit[nx] = True

        arr[nx] = arr[x] + 1

        q.append((nx))

이차원 배열에서 일차원 배열로 수정한 코드이다.

조건은 똑같이 검사하고 달라진 점이라면 배열의 1차원화 뿐이다.

그런데도 한번에 통과했다.

참 멍청했다..