[python] BOJ 백준 23288: 주사위굴리기2

1. 문제  

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다. 주사위 한 면의 크기와 지도 한 칸의 크기는 같고, 주사위의 전개도는 아래와 같다.

  2
4 1 3
  5
  6

주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (1, 1) 이다. 지도의 각 칸에도 정수가 하나씩 있다. 가장 처음에 주사위의 이동 방향은 동쪽이다. 주사위의 이동 한 번은 다음과 같은 방식으로 이루어진다.

1. 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
2. 주사위가 도착한 칸 (x, y)에 대한 점수를 획득한다.
3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
   • A > B인 경우 이동 방향을 90도 시계 방향으로 회전시킨다.
   • A < B인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
   • A = B인 경우 이동 방향에 변화는 없다.

칸 (x, y)에 대한 점수는 다음과 같이 구할 수 있다. (x, y)에 있는 정수를 B라고 했을때, (x, y)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수 C를 모두 구한다. 이때 이동할 수 있는 칸에는 모두 정수 B가 있어야 한다. 여기서 점수는 B와 C를 곱한 값이다.

보드의 크기와 각 칸에 있는 정수, 주사위의 이동 횟수 K가 주어졌을때, 각 이동에서 획득하는 점수의 합을 구해보자.

2. 입력   

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (2 ≤ N, M ≤ 20), 그리고 이동하는 횟수 K (1 ≤ K ≤ 1,000)가 주어진다.

둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 지도의 각 칸에 쓰여 있는 수는 10 미만의 자연수이다.

3. 출력   

첫째 줄에 각 이동에서 획득하는 점수의 합을 출력한다.

 

4. 해결방법   

시뮬레이션과 BFS로 풀수 있는 문제이다. 다만 주사위 굴리는 부분에 대해서는 기존에 출제된 적이 있기 때문에 주사위굴리기1 문제를 먼저풀고 이 문제를 푸는 것이 좋다. 해당 문제에 대한 풀이는 밑의 링크에서 확인할 수 있다. 

https://yeon-code.tistory.com/63

[python] BOJ 백준 14499: 주사위 굴리기

주사위 굴리기 1의 문제와 다른점은 점수를 더하는 과정에서 BFS 알고리즘이 추가로 쓰인다는 것이다. 동서남북 방향으로 같은 숫자를 가진 칸의 개수를 구하려면 BFS또는 DFS를 이용하여 탐색할수밖에 없다. 

1) dfs 함수: 큐에 현재좌표를 넣은 다음 동서남북으로 탐색하면서, 한번도 방문하지 않았고 + 보드판의 수가 현재 값과 같다면 그 좌표도 큐에 넣어주면서 갯수를 세어주면된다. 다만 주의할 점은, 카운트를 0부터 시작하여야 한다는 점이다. 동서남북 아무도 자신의 값과 같지 않은 경우에는 while 문을 한번만 돌고 끝나기 때문에 카운트 수가 증가하지 않는다. 만약 동서남북으로 자신이 값이 같아서 큐를 여러번 도는 경우에는 카운트수가 증가한다. 이 경우에 카운트 수를 0으로 초기화해준다음, 리턴값에 1을 더해주어야 두 상황에서 올바를 카운트 값을 구할 수 있다. 첫 카운트수를 1로 초기화하면 두 상황에서 올바른 카운트수를 구할 수 없다. 

2) 메인함수는 문제에서 요구한 순서와 똑같이 작성하면된다. 주사위를 굴리는 방향에 따라 주사위의 아랫면이 달라지기 때문에 4가지 방향에 따라서 다르게 구현을 해주어야한다. 이 부분에 대해서는 주사위 굴리기 1의 문제를 먼저 풀어보는 것을 추천한다. 주사위를 굴린 후에는 아랫면에 있는 정수와 주사위가 있는 칸의 정수를 비교하여 이동방향을 바꾸어주면된다. 

 

5) 구현코드       

from collections import deque

#동, 북, 서, 남 (반시계방향)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

n, m, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dice = [1,2,3,4,5,6]
x,y,d,score=0,0,0,0

def bfs(x,y,k):
  visited=set()
  visited.add((x,y))
  q=deque()
  q.append((x,y))
  cnt=0
  while q:
    x,y=q.popleft()
    for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if 0<=nx<n and 0<=ny<m:
        if (nx,ny) not in visited and board[nx][ny]==k:
          cnt+=1
          visited.add((nx,ny))
          q.append((nx,ny))
  return cnt

for i in range(k):

    if not 0 <=  x + dx[d] < n or not 0 <= y + dy[d]< m:
        d=(d+2)%4 #반대방향으로 바꿔주기 
    x,y = x + dx[d] , y + dy[d] #한칸이동 
    
    score+= (bfs(x,y,board[x][y])+1) * board[x][y] #점수계산 
    if d == 0: #동쪽
        dice[0], dice[2], dice[3], dice[5] = dice[3], dice[0], dice[5], dice[2]
    elif d == 1: #북쪽
        dice[0], dice[1], dice[4], dice[5] = dice[1], dice[5], dice[0], dice[4]
    elif d == 2: #서쪽
        dice[0], dice[2], dice[3], dice[5] = dice[2], dice[5], dice[0], dice[3]
    elif d == 3: #남쪽
        dice[0], dice[1], dice[4], dice[5] = dice[4], dice[0], dice[5], dice[1]
    

    if dice[5]>board[x][y]:
        d=(d+1)%4 #90도 시계방향 
    elif dice[5]<board[x][y]:
        d=(d+3)%4 #90도 반시계방향 

print(score)

 

⭐️난이도:  골드 3⭐️ 

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

23288번: 주사위 굴리기 2