[백준 17825번] 주사위 윷놀이(파이썬)

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

17825번: 주사위 윷놀이

우선 그림을 보자마자

이게 뭔가 싶은 문제입니다.

보통 길찾기문제라면

좌표평면이라든가

사각형좌표로 많이 있는데

이건 뭐지...

싶었던 문제.

말을 움직이는 케이스는

dfs로 풀면 됩니다.

2022.03.06 - [알고리즘 공부] - [백준 14888번] 연산자 끼워넣기

[백준 14888번] 연산자 끼워넣기

저는 이 문제를 풀 때

이 문제를 풀었던 경험이 떠올라서

dfs로 푼다는 것 까지 떠올랐네요.

문제는 저 주사위 지도를 어떻게 구현해서 푸냐는 겁니다.

저는 처음 풀었을 때

큰 거 하나(0~40)

파란거 각각 3개

(10,13....)

(30,28....)

(20,22....)

 

이렇게 나누는 것까지는 생각이 나는데

중간에 합쳐지는 부분 구현을 제대로 못했네요.

그리고 맨날 visited리스트를 만들어서

말이 있는지 여부를 판단했는데

이 문제는 각각의 지도가 나뉘어져 있어서

그렇게 풀면 안되는 문제였습니다.

 

인터넷의 솔루션을 참고한 코드입니다.

 

#백준 17825 주사위 윷놀이
import sys
input=sys.stdin.readline

piece=[0 for i in range(11)]
dice_map=[
          [i for i in range(0,42,2)],
          [10,13,16,19],
          [30,28,27,26,25],
          [20,22,24,25,30,35,40],
          ]
position=[
          [i for i in range(21)],
          [5,21,22,23],
          [15,24,25,26],
          [10,27,28,29,30,31,20]
          ]
#주사위의 숫자와 그에 맞는 포지션을 각각 구현한

def score():
  global result
  pi_po=[[0,0] for i in range(5)]
  num=0
  for i in range(1,11):
    pi=piece[i]
    x,y=pi_po[pi]
    #이미 나간 것은 계산하지 않
    if x==-1:return
    else:
      y+=s[i]
      if x==0:
        if 20<y:
          pi_po[pi]=[-1,-1]
          #범위를 넘어갔으므로 도착한 걸로 한다
        elif y==5:
          #5에 들어가면 위치 점프
          pi_po[pi]=[1,0]
        elif y==10:
          pi_po[pi]=[3,0]
        elif y==15:
          pi_po[pi]=[2,0]
        else:
          pi_po[pi]=[x,y]
      elif x==1:
        if y>=8:
          pi_po[pi]=[-1,-1]
        elif y>=4:
          pi_po[pi]=[3,y-1]
        else:
          pi_po[pi]=[x,y]
      elif x==2:
        if y>=8:
          pi_po[pi]=[-1,-1]
        elif y>=4:
          pi_po[pi]=[3,y-1]
        else:
          pi_po[pi]=[x,y]
      elif x==3:
        if y>6:
          pi_po[pi]=[-1,-1]
        else:
          pi_po[pi]=[x,y]
      nx,ny=pi_po[pi]
      if nx!=-1:
        for k in range(1,5):
          if pi==k:
            continue
          a,b=pi_po[k]
          if a==-1:
            continue
          if position[a][b]==position[nx][ny]:
            #도착한 곳에 이미 다른 말이 있을 경우
            #움직이면 안되니 return시켜준다(무효시켜준다)
            return
        num+=dice_map[nx][ny]
  result=max(result,num)

#dfs를 통해 모든 경우의 수를 백트래킹하여 구한다
def dfs(depth):
  if depth==10:
    score()
    return
  for i in range(1,5):
    depth+=1
    piece[depth]=i
    #piece에다가 각 명령어에 몇번째 말을 움직일지 넣어준다.
    dfs(depth)
    depth-=1
s=[0]+list(map(int,input().split()))
result=0
depth=0
dfs(depth)
print(result)

 

이 솔루션을 토대로보면

지도+그에맞는 위치를

각각 구현을 해놨음을 볼 수 있었습니다.

그리고 굳이 visited를 따로 만들지 않더라도

이전에 옮긴 말의 숫자를 보고

return시킬 수 있네요.

 

https://juhi.tistory.com/52

[Python] 백준 17825: 주사위 윷놀이

이 풀이도 공부할 것이 상당했습니다.

 

이런 당황스럽게 보이는 구현을 풀 때

문제에서 요구하는 그림을

차근차근 그리면서

조건에 만족하는 식으로 접근해야겠구나

라는 깨달음을 많이 받았습니다.

 

++++

#백준 17825 주사위 윷놀이

dice=list(map(int,input().split()))
#0 큰 거
#1 13 16 19
#2 22 24 25 30 35
#3 28,27,26
graph=[
    [i for i in range(0,42,2)],
    [10,13,16,19],
    [20,22,24,25,30,35],
    [30,28,27,26]
]

horse=[[0,0] for _ in range(4)]


answer=0
trace=[]

def dfs(nums,now_sum):
    global answer,trace
    if nums==10:
        answer=max(answer,now_sum)
        return
    #4개 중 하나를 움직인다
    for d in range(4):
        #다 움직인 말은 제외한다.

        tmp=horse[d]
        now=horse[d][1]
        if now==40:
            continue
        now+=dice[nums]
        #0을 움직이는 경우
        if horse[d][0]==0:
            #10에 안착
            if now==5:
                if [1,0] in horse:
                    continue
                horse[d]=[1,0]
            #20에 안착
            elif now==10:
                if [2,0] in horse:
                    continue
                horse[d]=[2,0]
            #30에 안착
            elif now==15:
                if [3,0] in horse:
                    continue
                horse[d]=[3,0]

            elif now>=21:
                horse[d]=[0,40]
            else:
                if [0,now] in horse:
                    continue
                horse[d]=[0,now]
        #1를 움직이는 경우
        elif horse[d][0]==1:
            #40에 안착한 경우
            if now>7:
                horse[d]=[0,40]
            elif now==7:
                if [0,20] in horse:
                    continue
                horse[d]=[0,20]
            elif 4<=now<7:
                if [2,now-1] in horse:
                    continue
                horse[d]=[2,now-1]
            else:
                if [1,now] in horse:
                    continue
                horse[d]=[1,now]
        #2를 움직이는 경우
        elif horse[d][0]==2:
            if now>6:
                horse[d]=[0,40]
            elif now==6:
                if [0,20] in horse:
                    continue
                horse[d]=[0,20]
            else:
                if [2,now] in horse:
                    continue
                horse[d]=[2,now]
        #3을 움직이는 경우
        elif horse[d][0]==3:
            if now>7:
                horse[d]=[0,40]
            elif now==7:
                if [0,20] in horse:
                    continue
                horse[d]=[0,20]
            elif 4<=now<7:
                if [2,now-1] in horse:
                    continue
                horse[d]=[2,now-1]
            else:
                if [3,now] in horse:
                    continue
                horse[d]=[3,now]
        if horse[d][1]==40:
            plus=0
        else:
            plus=graph[horse[d][0]][horse[d][1]]
        trace.append([d,horse[d],plus])
        dfs(nums + 1,now_sum+plus)
        horse[d] = tmp
        trace.pop()
dfs(0,0)
print("{}".format(answer))

스스로 다시 푼 코드입니다.

우선 다시 풀 떄에도 상당히 헷갈리는 점을 발견했습니다.

 

바로 40에서 겹쳐지는 부분입니다.

저는 파란색 화살표가 있는

10 20 30이

25에서 합쳐지는 것까지는 구현했고

20 22 24 25 30 35 40

이렇게 구현했습니다.

이렇게 구현하면 이런 문제가 생깁니다.

문제요구대로라면은

40에 말이 올려져있으면

다른 말이 이동하지 못하는 것이 정상입니다.

하지만 저는 처음에

20 22....40으로 두어서

큰 원과 합쳐지 않은 걸로 구현했었습니다.

그러니, 컴퓨터가 인식하기에는

'둘이 다른 위치에 있다'라고 인식하게 되어서

NG가 발생했습니다.

실제로 이런 부분 때문에

예제3만 이상이 생겨 상당히 난감했습니다.

이 사실을 발견한 이후에 1,2,3을 돌 떄

now가 6,7일 때

[0,20]이 있는지 판단한 이유도

0의 20번째칸은 40이기 때문에

합쳐지는 걸 나름대로 구현한 것입니다.

https://www.acmicpc.net/board/view/89398

글 읽기 - 아마 다들 여기서 틀렸을 것 같아서 공유

실제로 질문게시판에 있는 글입니다.

이 문제의 맞왜틀이 반복되신다면

합쳐지는 걸 다시 한번 보시는 걸 권해드립니다.

 

(내용추가:2022.10.12)

from copy import deepcopy

nums=list(map(int,input().split()))
mapping=[[i for i in range(0,42,2)],
        [10,13,16,19,25,30,35],
         [20,22,24],
         [30,28,27,26]
         ]

#말의 구역과 현재 숫자 넣어줌
horse=[[0,0] for _ in range(4)]
answer=0

def dfs(depth,score):
    global answer,horse
    if depth==10:
        answer=max(answer,score)

        return

    temp=deepcopy(horse)
    now=nums[depth]
    #현재 숫자를 기준으로 말을 하나씩 움직인다고 가정
    for d in range(4):

        now_group=horse[d][0]
        now_on=horse[d][1]

        #이미 도착한 건 배제
        if now_group==-1:
            continue
        #첫번째 큰 그룹이라면
        if now_group==0:
            now_on+=now
            #도착한 경우
            if now_on>=21:
                next_group=-1

            #30에 도착한 경우
            elif now_on==15:
                next_group=3
                next_num=0

            #20에 도착한 경우
            elif now_on==10:
                next_group=2
                next_num=0

            #10에 도착한 경우
            elif now_on==5:
                next_group=1
                next_num=0
            #그자리 그대로
            else:
                next_group=0
                next_num=now_on

        #두번쨰 그룹이라면
        elif now_group==1:
            now_on+=now
            #도착지점에 간 경우라면
            if now_on>=8:
                next_group=-1
                next_num=-1

            #40에 있는 경우
            elif now_on==7:
                next_group=0
                next_num=20
            #그 외의 경우
            else:
                next_group=1
                next_num=now_on

        #세번쨰 그룹이라면
        elif now_group == 2:
            now_on += now
            # 도착지점에 간 경우라면
            if now_on >= 7:
                next_group = -1
                next_num = -1
            #40을 밟을때
            elif now_on==6:
                next_group=0
                next_num=20
            #25를 밟고 가는 경우라면
            elif 3<=now_on<=5:
                next_group=1
                next_num=now_on+1
            else:
                next_group = 2
                next_num = now_on
        #네번쨰 그룹이라면
        elif now_group==3:
            now_on += now
            # 도착지점에 간 경우라면
            if now_on >= 8:
                next_group = -1
                next_num = -1
            #40에 왔다면
            elif now_on==7:
                next_group=0
                next_num=20

            #25밟았다면
            elif 4<=now_on<=6:
                next_group=1
                next_num=now_on
            # 그게 아니라면
            else:
                next_group = 3
                next_num = now_on

        #현재 이미 도착한 상태
        if next_group==-1:
            horse[d]=[-1,-1]
            dfs(depth+1,score)
            horse=deepcopy(temp)
        #만약 도착이 아니라면
        else:
            #다른 말이 그쪽에 없다면
            if not [next_group,next_num] in horse:
                next_score=score+mapping[next_group][next_num]
                #print(mapping[next_group][next_num],now_group,next_group,next_num,now)
                horse[d]=[next_group,next_num]
                dfs(depth+1,next_score)
                horse=deepcopy(temp)


dfs(0,0)
print(answer)

 

다시 풀어본 코드

역시나 이번에도

겹쳐지는 부분을 처음에 고려하지 않아서

'이게 왜...'라면서 조금 헤메다가

겹쳐질 수 있다는 걸 생각하고 코드를 수정했습니다.

이 코드는 심신노약자 제출 비권장인데요...

pypy3로 제출했더니

체점하는데만 3분 걸린거 같네요.

1%가 느릿느릿 올라가는 걸 바라보면서

혹시나 시간초과or 틀렸습니다 뜰까봐

조마조마하는 나를 알까?