문제
문제는 다음과 같다.
14499번 주사위 굴리기 문제와 유사하다.
풀이
dir이라는 변수에 방향 정보를 저장한다. 0, 1, 2, 3이 각각 동, 남, 서, 북을 나타낸다.(시계방향 순서)
dir_dx = [0, 1, 0, -1]
dir_dy = [1, 0, -1, 0]
reverse_dir = {0:2, 1:3, 2:0, 3:1}
dir = 0 # 동쪽- 이동할 수 없는 경우 방향을 뒤집어야 하는데, 이 때 사용하려고 reverse_dir를 만들었다. 그냥 dx, dy에 -1을 곱해줘도 된다.
주사위는 이 구조를 유지한다고 생각하면 쉽다.
여기에 써진 숫자는, 주사위 구조에서의 위치를 나타낸다고 생각하자.
-
처음에는 1이 가장 위로 오도록 주사위가 놓여있다.
-
오른쪽(동쪽)으로 굴린 경우
- 1의 위치에 4, 2의 위치에 2, 3의 위치에 1, 4의 위치에 6, 5의 위치에 5, 6의 위치에 3이 온다.
- 이걸 코드로 나타내면 다음과 같다.
if dir == 0: # 동
dice = [0, dice[4], dice[2], dice[1], dice[6], dice[5], dice[3]]모든 방향에 대해서도 똑같이 구하면, 주사위를 굴리는 roll 함수는 아래와 같이 작성할 수 있다.
def roll(dir):
global dice
if dir == 0: # 동
dice = [0, dice[4], dice[2], dice[1], dice[6], dice[5], dice[3]]
elif dir == 1: # 남
dice = [0, dice[2], dice[6], dice[3], dice[4], dice[1], dice[5]]
elif dir == 2: # 서
dice = [0, dice[3], dice[2], dice[6], dice[1], dice[5], dice[4]]
elif dir == 3 : # 북
dice = [0, dice[5], dice[1], dice[3], dice[4], dice[6], dice[2]]
return dice[6]현재 칸에 대한 점수를 구하기 위해서는, 현재 칸과 같은 숫자를 가진 인접한 칸의 수를 구하면 된다. 따라서 bfs를 사용하여 쉽게 구할 수 있다.
def bfs(i, j, k):
cnt = 0
q = deque([[i, j]])
visited = [[False for _ in range(m)] for _ in range(n)]
visited[i][j] = True
while q:
x, y = q.popleft()
cnt += k
for dx, dy in (x+1, y), (x-1, y), (x, y+1), (x, y-1):
if 0 <= dx < n and 0 <= dy < m:
if visited[dx][dy] == False and board[dx][dy] == k:
q.append([dx, dy])
visited[dx][dy] = True
return cnt정답 코드
from collections import deque
n, m, k = map(int, input().split())
board = []
for _ in range(n):
board.append(list(map(int, input().split())))
dice = [0, 1, 2, 3, 4, 5, 6]
dir_dx = [0, 1, 0, -1]
dir_dy = [1, 0, -1, 0]
reverse_dir = {0:2, 1:3, 2:0, 3:1}
dir = 0 # 동쪽
x, y = 0, 0
floor = 6 # 주사위 밑면
def roll(dir):
global dice
if dir == 0: # 동
dice = [0, dice[4], dice[2], dice[1], dice[6], dice[5], dice[3]]
elif dir == 1: # 남
dice = [0, dice[2], dice[6], dice[3], dice[4], dice[1], dice[5]]
elif dir == 2: # 서
dice = [0, dice[3], dice[2], dice[6], dice[1], dice[5], dice[4]]
elif dir == 3 : # 북
dice = [0, dice[5], dice[1], dice[3], dice[4], dice[6], dice[2]]
return dice[6]
def bfs(i, j, k):
cnt = 0
q = deque([[i, j]])
visited = [[False for _ in range(m)] for _ in range(n)]
visited[i][j] = True
while q:
x, y = q.popleft()
cnt += k
for dx, dy in (x+1, y), (x-1, y), (x, y+1), (x, y-1):
if 0 <= dx < n and 0 <= dy < m:
if visited[dx][dy] == False and board[dx][dy] == k:
q.append([dx, dy])
visited[dx][dy] = True
return cnt
score = 0
for _ in range(k):
if (not 0 <= x + dir_dx[dir] < n) or (not 0 <= y + dir_dy[dir] < m): # 반대방향으로
dir = reverse_dir[dir]
x, y = x + dir_dx[dir], y + dir_dy[dir] # 이동
floor = roll(dir)
if floor > board[x][y]:
dir = dir+1 if dir < 3 else 0
elif floor < board[x][y]:
dir = dir-1 if dir > 0 else 3
#점수 계산
score += bfs(x, y, board[x][y])
print(score)k = 1000, n*m = 400이라고 할 때, 최악의 경우는 BFS를 1000번 수행하는 것이고, O(1000 * (400^2))의 시간이 걸린다.
