문제
지도 배열 위에서 주사위를 굴리는 구현 문제 + 서로 점수가 같은 칸끼리 얼마나 이어져있는지 찾는 그래프 탐색
풀이
문제에서 주어진 순서대로 풀었다
- 주사위를 한 칸 굴린다.
- 점수를 획득한다
- 주사위의 바닥면 값과 칸의 값을 비교해서 방향을 결정한다
주사위 굴리기(tumble)
-
이렇게 생긴 주사위를 '굴린다'는 걸 어떻게 구현해야 할 지 막막했는데 일단 숫자가 6까지 있으니까 배열에 넣어보자 해서 배열에 넣었다
[0, 1, 2, 3, 4, 5] -
이렇게 되면 서로 마주보고 있는 면에 있는 숫자들의 합이 5가 된다. 처음엔 이걸 이용해서 어떻게 풀 수 있을 줄 알았는데
이런 식으로 동쪽(오른쪽그림), 남쪽(아래쪽그림)으로 굴리게 되면 주사위에서 4개의 면 위치가 변한다. 어떤 규칙적인 게 없고 동서남북 방향에 따라 변화하는 면들이 서로 다르기 때문에 어쩔 수 없이 각 방향에 따라 바뀐 면을 통째로 반환하는 형식으로 함수를 짰다.
-
우선 가장 위의 그림과 같은 순서로 주사위가 배치되어 있다고 치자. 가장 위에 있는 면이 0, 가장 바닥에 있는 면이 인덱스 5의 값을 가진다.
def tumble(D, a, b, c, d, e, f):
if D == 0:
return d, b, a, f, e, c
elif D == 1:
return b, f, c, d, a, e
elif D == 2:
return c, b, f, a, e, d
elif D == 3:
return e, a, c, d, f, b- 동쪽인 0으로 시작으로 90도 방향으로 꺾여서 동 남 서 북으로 차례대로 값을 반환하게 된다.
점수 획득(score)
- 점수 획득의 경우 너비 우선 탐색으로 현재 위치한 칸의 값과 인접한 칸들 가운데 같은 값을 가진 칸의 개수를 구했다
# 점수 획득
def score(x, y):
global ans
B, C = MAP[x][y], 1
q = [(x, y)]
visit[x][y] = K
while q:
x, y = q.pop(0)
# 동서남북 방향으로 연속해서 이동할 수 있는지
for nx, ny in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
# 이동할 수 있는 칸의 값은 모두 B여야 하고 방문한 적이 없어야 함
if -1<ny<M and -1<nx<N and MAP[nx][ny] == B and visit[nx][ny] != K:
C += 1
visit[nx][ny] = K
q.append((nx, ny))
ans += B * C- 근데 이 방식은 시간이 굉~장히 오래 걸리는 거였다.. ㅠㅠ
애초에 배열이 변화하지 않기 때문에 굳이 주사위가 구를 때마다 bfs를 해줄 필요가 없었다.. 미리 bfs로 이 칸과 같은 값을 가지는 인접한 칸의 개수를 구해준 다음에 주사위가 굴러서 그 칸에 위치하면 그때 그 값을 가져와서 점수에 더해주기면 하면 되는 것이었당
# 점수 획득
def bfs(x, y, B):
q = [(x, y)]
idx = 0
while idx<len(q):
x, y = q[idx]
idx += 1
# 동서남북 방향으로 연속해서 이동할 수 있는지
for nx, ny in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
# 이동할 수 있는 칸의 값은 모두 B여야 하고 방문한 적이 없어야 함
if -1<ny<M and -1<nx<N and MAP[nx][ny] == B and (nx, ny) not in q:
q.append((nx, ny))
for _x, _y in q:
MAP[_x][_y] = (B, len(q))방향 결정
- 단순 조건문만 사용하면 됨
def move(A, B, d):
if A > B:
return (d+1)%4
elif A < B:
return (d+3)%4
return d최종 코드
- 리팩토링 전은 360ms, 후는 48ms로 시간 복잡도가 1/9로 줄어든다
리팩토링 전
import sys
input = sys.stdin.readline
# 점수 획득
def score(x, y):
global ans
B, C = MAP[x][y], 1
q = [(x, y)]
visit[x][y] = K
while q:
x, y = q.pop(0)
# 동서남북 방향으로 연속해서 이동할 수 있는지
for nx, ny in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
# 이동할 수 있는 칸의 값은 모두 B여야 하고 방문한 적이 없어야 함
if -1<ny<M and -1<nx<N and MAP[nx][ny] == B and visit[nx][ny] != K:
C += 1
visit[nx][ny] = K
q.append((nx, ny))
ans += B * C
def move(A, B, d):
if A > B:
return (d+1)%4
elif A < B:
return (d+3)%4
return d
def tumble(D, a, b, c, d, e, f):
if D == 0:
return d, b, a, f, e, c
elif D == 1:
return b, f, c, d, a, e
elif D == 2:
return c, b, f, a, e, d
elif D == 3:
return e, a, c, d, f, b
def sol():
global K
dice = [d for d in range(1, 7)]
x = y = d = 0
while K:
# 1. 주사위가 이동 방향으로 한 칸 굴러간다
nx, ny = x+dx[d], y+dy[d]
# 만약, 이동 방향에 칸이 없다면 이동 방향을 반대로 한 다음에 한 칸 굴러간다
if ny<0 or nx<0 or ny>=M or nx>=N:
d = (d+2)%4
nx, ny = x+dx[d], y+dy[d]
dice = list(tumble(d, *dice))
# print(dice)
x, y = nx, ny
# 2. 주사위가 도착한 칸에 대한 점수를 획득한다
score(x, y)
# 3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸의 값을 비교해서 이동방향 결정
d = move(dice[-1], MAP[x][y], d)
# 주사위 이동 횟수 차감
K -= 1
N, M, K = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(N)]
dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
visit = [[0]*M for _ in range(N)]
ans = 0
sol()
print(ans)리팩토링 후
import sys
input = sys.stdin.readline
# 점수 획득
def bfs(x, y, B):
q = [(x, y)]
idx = 0
while idx<len(q):
x, y = q[idx]
idx += 1
# 동서남북 방향으로 연속해서 이동할 수 있는지
for nx, ny in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
# 이동할 수 있는 칸의 값은 모두 B여야 하고 방문한 적이 없어야 함
if -1<ny<M and -1<nx<N and MAP[nx][ny] == B and (nx, ny) not in q:
q.append((nx, ny))
for _x, _y in q:
MAP[_x][_y] = (B, len(q))
def move(A, B, d):
if A > B:
return (d+1)%4
elif A < B:
return (d+3)%4
return d
def tumble(D, a, b, c, d, e, f):
if D == 0:
return d, b, a, f, e, c
elif D == 1:
return b, f, c, d, a, e
elif D == 2:
return c, b, f, a, e, d
elif D == 3:
return e, a, c, d, f, b
def sol():
global K
dice = [d for d in range(1, 7)]
x = y = d = ans = 0
while K:
# 1. 주사위가 이동 방향으로 한 칸 굴러간다
nx, ny = x+dx[d], y+dy[d]
# 만약, 이동 방향에 칸이 없다면 이동 방향을 반대로 한 다음에 한 칸 굴러간다
if ny<0 or nx<0 or ny>=M or nx>=N:
d = (d+2)%4
nx, ny = x+dx[d], y+dy[d]
dice = list(tumble(d, *dice))
# print(dice)
x, y = nx, ny
# 2. 주사위가 도착한 칸에 대한 점수를 획득한다
B, C = MAP[x][y]
ans += B*C
# 3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸의 값을 비교해서 이동방향 결정
d = move(dice[-1], B, d)
# 주사위 이동 횟수 차감
K -= 1
return ans
N, M, K = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(N)]
dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
visit = [[0]*M for _ in range(N)]
for i in range(N):
for j in range(M):
if type(B:=MAP[i][j]) == int:
bfs(i, j, B)
print(sol())
아무말이나하기