[삼성SW역량][Python/BOJ] 백준 23288 주사위굴리기2_(구현+BFS)

 

 

 

이 그림처럼 주사위를 기본으로 생각하면 된다. 다만 위치는 해당 값 -1으로 

3은 동쪽을 1은 아래 쪽을 가리킨다. 

 

처음에 이 기본 주사위의 1이 천장에 있는 줄 알고  풀었다가 시간을 오래 끌었다. 

 

 

 

 

기본 주사위 굴리기 문제에서 BFS가 추가된 문제이다. 

해당 주사위 칸에서 BFS를 돌려 숫자가 같은 것의 개수와 해당 주사위 칸의 값의 총합을 출력하는 문제다. 

 

 

 

위 그림에서 0이면 오른쪽으로 돌려서 생각해보면 된다.

위 그림에서 오른쪽으로 돌리는 주사위로 변한 위치를 대입해준다. [리스트는 0-index이기 때문에 1을 빼준다.)

 

 

그러면 5와 2는 그대로이므로 4631 (기본) ->  1463 이 된다. 

각각 1을 빼주면 3520 -> 0352가 된다. 그게 바로 밑 코드의 dir == 0인 경우다.  

 

코드 : 

from collections import deque
from itertools import combinations as c 

# 동 남 서 북 
dx= [0,1,0,-1]
dy = [1,0,-1,0]


def bfs(x,y,num) :
    vis = [[0]*m for i in range(n)]
    d = deque([[x,y]])
    vis[x][y] = 1
    cnt =1 
    while d:
        x,y = d.popleft()
        for i in range(4) :
            nx,ny = x + dx[i],y + dy[i]
            if 0<=nx<n and 0<=ny<m and mp[nx][ny] == num and vis[nx][ny] == 0 :
                vis[nx][ny] = 1 
                cnt +=1 
                d.append([nx,ny])
    return cnt 


if __name__=="__main__" :
    n,m,k = map(int,input().split())
    mp = [list(map(int,input().split())) for i in  range(n)]
    ans = 0
    dice = [1,2,3,4,5,6]
    dir,x,y = 0,0,0
    
    # k 번 주사위 던진다. 
    for _ in range(k) :
        # 범위가 넘어가면 
        if not 0<=x + dx[dir]<n or not 0<=y + dy[dir]<m :
            # 방향을 반대로 
            dir = (dir+2)%4
        x,y = x + dx[dir], y + dy[dir]
        
        if dir == 0 : # 동 
            dice[3],dice[5],dice[2],dice[0] = dice[5],dice[2],dice[0],dice[3]
        elif dir == 1 : # 남 
            dice[1],dice[5],dice[4],dice[0] = dice[5],dice[4],dice[0],dice[1]
        elif dir == 2 : # 서 
            dice[2],dice[0],dice[3],dice[5] =  dice[5],dice[2],dice[0],dice[3]
        else : # 북 
            dice[4],dice[0],dice[1],dice[5] = dice[5],dice[4],dice[0],dice[1]
            
        A = dice[5]
        B = mp[x][y] 
        if A > B : dir = (dir+1)%4 
        elif A<B : dir = (dir+3)%4 

        # 도착한 칸에 대한 점수 
        ans += (bfs(x,y,mp[x][y]) * B)
    print(ans)

 

 

 

 

 

참고 블로그 : 

https://chldkato.tistory.com/196

백준 23288 주사위 굴리기 2 (파이썬)