23288: 주사위 굴리기 2

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

23288번: 주사위 굴리기 2

설명

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 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가 주어졌을때, 각 이동에서 획득하는 점수의 합을 구해보자.

이 문제의 예제 1부터 7은 같은 지도에서 이동하는 횟수만 증가시키는 방식으로 구성되어 있다. 예제 8은 같은 지도에서 이동하는 횟수를 매우 크게 만들었다.

핵심 아이디어

• 문제를 읽으면서 차례대로 구현하면 된다.
• k번 만큼 주사위를 굴린다.
  • 이때, 만약 이동방향에 칸이 없다면 반대 방향으로 굴린다. -> 원래 방향의 값에 -1을 곱해준 값을 더해주면 된다.
  • 그리고 방향을 바꿔준다. 예를들어, 동쪽으로 굴렸는데 칸이 없다면 서쪽으로 굴린 후, 현재 방향을 서쪽으로 변경
  • 그 후 지도의 값과 주사위 값을 비교해 이동방향을 바꿔준다. -> 인덱스 값으로 처리
• 마지막에 점수를 구해준다.
  • BFS를 이용해서 이동 가능한 칸 값이 주사위를 이동시켰을 때의 지도값과 같으면 더 해 준다.

코드 구현

1. 주사위가 이동방향으로 굴러하는 코드

만약, 이동방향에 칸이 없다면 이동방향 반대로 한 다음 한칸 굴러간다. 

ans = 0
for _ in range(k):
    nx = x + dx[direction]
    ny = y + dy[direction]
    # 만약 이동 방향에 칸이 없다면
    if x < 0 or x >= n or y < 0 or y >= m:
        nx = x + dx[direction] * (-1)
        ny = y + dy[direction] * (-1)
        direction = (direction + 2) % 4  # 해당 방향으로 현재 방향 변경
    # 주사위 굴리고 방향 다시 설정
    direction = turn(direction, nx,ny) # 주사위 아랫면과 칸의 정수 비교해서 결정
    # 점수 계산
    ans += get_score(nx,ny)
    # 현재 좌표 업데이트
    x,y = nx,ny
print(ans)

2. 주사위 굴리고 방향 다시 설정하는 함수 정의

def tunr(direction, x,y):
    global dice
        # 동쪽
    if direction == 0:
        dice = [dice[3], dice[1], dice[0], dice[5], dice[4], dice[2]]
    # 남쪽
    elif direction == 1:
        dice = [dice[1], dice[5], dice[2], dice[3], dice[0], dice[4]]
    # 서쪽
    elif direction == 2:
        dice = [dice[2], dice[1], dice[5], dice[0], dice[4], dice[3]]
    # 북쪽
    else:
        dice = [dice[4], dice[0], dice[2], dice[3], dice[5], dice[1]]
    # A(주사위의 아랫면) > B(격자 칸의 정수) -> 90도 시계 방향
    if dice[-1] > graph[x][y]:
        direction = (direction + 1) % 4
    elif dice[-1] < graph[x][y]:
        direction = (direction - 1) % 4
    return direction

3. 점수를 더하는 함수 -> BFS

def get_score(x,y):
    # 똑같은 곳을 다시 더하지 않기 위해
    visited = [[False] * m for _ in range(n)]
    q = deque()
    q.append((x,y))
    visited[x][y] = True
    
    score_sum = 0
    
    while q:
        x,y = q.popleft()
        score_sum += graph[x][y]
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if (0<=nx<n) and (0<=ny<n) and not visited[nx][ny]:
                # 이전칸의 정수와 같다면
                if graph[nx][ny] == graph[x][y]
                    visited[nx][ny] = True
                    q.append((nx,ny))
                    
    return score_sum

4. 최종 결과

from collections import deque
import sys
input = sys.stdin.readline
n,m,k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

# 주사위 초기상태: 윗면, 북, 동, 서, 남, 아래
dice = [1,2,3,4,5,6]
# 동 남 서 북 -> 0 1 2 3
x,y,direction = 0,0,0
# 이동을 위한 방향 정의  동 남 서 북
dx = [0,1,0,-1]
dy = [1,0,-1,0]
# 주사위 굴리는 함수 정의
def turn(direction, x, y):
    global dice

    # 동쪽
    if direction == 0:
        dice = [dice[3], dice[1], dice[0], dice[5], dice[4], dice[2]]
    # 남쪽
    elif direction == 1:
        dice = [dice[1], dice[5], dice[2], dice[3], dice[0], dice[4]]
    # 서쪽
    elif direction == 2:
        dice = [dice[2], dice[1], dice[5], dice[0], dice[4], dice[3]]
    # 북쪽
    else:
        dice = [dice[4], dice[0], dice[2], dice[3], dice[5], dice[1]]

    if dice[-1] > graph[x][y]:
        direction = (direction + 1) % 4
    elif dice[-1] < graph[x][y]:
        direction = (direction - 1) % 4

    return direction
# 점수를 계산하는 함수 정의
def get_score(x, y):
    # 똑같은 곳을 다시 더하지 않기 위해 배열 추가
    visited = [[False] * m for _ in range(n)]
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    score_sum = 0

    while queue:
        x,y = queue.popleft()
        score_sum += graph[x][y]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                if graph[nx][ny] == graph[x][y]:
                    queue.append((nx, ny))
                    visited[nx][ny] = True

    return score_sum

# 1. k번 주사위를 굴린다.
ans = 0
for _ in range(k):
	nx = x + dx[direction]
	ny = y + dy[direction]
	# 이동 방향에 칸이 없는 경우
	if nx < 0 or nx >= n or ny < 0 or ny >= m:
		# 반대 방향으로 굴린다.
		nx = x + dx[direction] * (-1)
		ny = y + dy[direction] * (-1)
		# 반대 방향으로 변경한다.
		direction = (direction + 2) % 4
	# 주사위 굴리고 방향 다시 설정
	direction = turn(direction, nx,ny)
	# 점수 계산
	ans += get_score(nx, ny)
	x,y = nx,ny # 해당 방향으로 굴러가고 현재 위치 업데이트

print(ans)

다른 풀이

import sys
input = sys.stdin.readline
from collections import deque
n,m,k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

# 방향정의 동 남 서 북 -> 0 1 2 3
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
# 기본 위치 정의
x,y,direction = 0,0,0
# 주사위 초기화
# 윗면, 북 동 서 남 아래
dice = [1,2,3,4,5,6]
# 이동 방향을 결정하는 함수
def turn(direction, x,y):
	global dice
	# 만약 동쪽으로 이동한다면
	if direction == 0:
		dice = [dice[3],dice[1],dice[0],dice[5],dice[4],dice[2]]
	elif direction == 1: # 남쪽 방향
		dice = [dice[1],dice[5],dice[2],dice[3],dice[0],dice[4]]
	elif direction == 2: # 서쪽
		dice = [dice[2],dice[1],dice[5],dice[0],dice[4],dice[3]]
	elif direction == 3: # 북쪽
		dice = [dice[4],dice[0],dice[2],dice[3],dice[5],dice[1]]

	# A > B인 경우 90도 시계 방향으로 회전시킨다.
	if dice[-1] > graph[x][y]:
		direction = (direction + 1) % 4
	elif dice[-1] < graph[x][y]:
		direction = (direction - 1) % 4
	return direction # 이동 방향 결정 한 것 반환
# 점수를 획득하는 함수 정의 -> BFS 함수 활용
def get_score(x,y):
	visited = [[False] * m for _ in range(n)]
	q = deque()
	q.append((x,y))
	# 현재 위치 방문 처리
	visited[x][y] = True
	C = 1
	B = graph[x][y]
	while q:
		x,y = q.popleft()
		for d in range(4):
			nx = x + dx[d]
			ny = y + dy[d]
			if (0<=nx<n) and (0<=ny<m) and not visited[nx][ny]:
				if B == graph[nx][ny]:
					C += 1
					visited[nx][ny] = True
					q.append((nx,ny))
	return B * C

# 각 이동에서 획득하는 점수의 합
ans = 0
for _ in range(k): # k번 만큼 주사위를 굴린다.
	# 이동방향 정의
	nx = x + dx[direction]
	ny = y + dy[direction]

	# 만약 이동 방향에 칸이 없다면 반대 방향으로 굴러간다.
	# 반대 방향 정의하기
	if nx < 0 or nx >=n or ny < 0 or ny >=m:
		nx = x + dx[direction] * (-1)
		ny = y + dy[direction] * (-1)
		# 방향도 동쪽에서 서쪽 방향으로 바꿔야한다.
		direction = (direction + 2) % 4 # 방향을 서쪽으로 돌린다.
	# 이 후 이동 방향 설정하기
	direction = turn(direction, nx,ny) # 이동 후 이동방향 결정하는 함수
	# 주사위가 도착한 칸에대한 점수를 획득한다.
	ans += get_score(nx,ny) # BFS 함수 정의
	# 이동하기
	x,y = nx,ny  # 실제 이동해서 현재 좌표를 업데이트한다.
print(ans)