문제
NxN개의 정사각형 구역으로 이루어진 정사각형 모양의 게임판이 세워져 있다. 각각의 구역은 비어있거나 벽으로 이루어져 있고, 빈 구역 중 하나에는 공이 놓여있다. 이 공은 중력의 영향을 받기 때문에 항상 벽이나 게임판의 바닥 위에 있게 된다.
우리는 게임판을 시계 방향 또는 시계 반대 방향으로 90도 회전시킬 수 있다. 이때 벽과 공도 게임판과 같이 회전하게 된다. 회전이 끝난 후에 공은 중력의 영향을 받아 벽이나 게임판의 바닥을 만날 때까지 떨어진다.
다음은 게임판을 시계 방향으로 회전시킨 후 시계 반대 방향으로 다시 회전시키는 예시이다.
게임판을 주어진 대로 회전시킨 이후의 상태를 출력하시오.
입력
첫째 줄에 게임판의 크기 N(1 ≤ N ≤ 1000)과 회전을 한 횟수 K(1 ≤ K ≤ 500,000)가 주어진다.
다음 N개의 줄에는 게임판의 초기 상태가 주어진다. 여기서 '.'은 빈 사각형, 'X'는 벽, 'L'은 공의 초기 위치를 의미한다.
이후 K개의 줄에는 각 단계에서의 회전 방향을 나타내는 'L' 또는 'D'가 주어진다. 'L'은 시계 반대 방향을 의미하고, 'D'는 시계 방향을 의미한다.
출력
주어진 K번의 회전을 순서대로 마친 후의 게임판의 상태를 N개의 줄에 걸쳐 출력한다.
문제 설명
게임판에 회전함에 따라 공이 어떻게 움직이는 지를 시뮬레이션하면 되는 문제이다.
사고과정
회전할 때마다 배열을 직접 회전시키면 시간초과가 날 것이 뻔하므로 마지막에만 회전시키는 방법을 쓰기로 했다.
코드
첫 코드
import sys
input = sys.stdin.readline
WALL = 'X'
BALL = 'L'
SPACE = '.'
D4 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def solve():
N, K = map(int, input().split())
arr = [[*input().rstrip()] for _ in range(N)]
cmds = [input()[0] for _ in range(K)]
# 처음 공의 위치를 찾는다
ball = []
for i, l in enumerate(arr):
for j, e in enumerate(l):
if e == BALL:
ball[:2] = i, j
arr[i][j] = SPACE
break
else:
continue
break
# 명령대로 회전시키고 중력을 적용한다
current = 1
for cmd in cmds:
if cmd == "D":
current -= 1
if current < 0:
current = 3
elif cmd == "L":
current += 1
if current > 3:
current = 0
# 중력 적용
while True:
i, j = ball[0] + D4[current][0], ball[1] + D4[current][1]
if not 0 <= i < N or not 0 <= j < N:
break
if arr[i][j] == WALL:
break
ball[:] = [i, j]
# 결과를 출력한다.
arr[ball[0]][ball[1]] = BALL
if current == 1:
for l in arr:
print(*l, sep="")
return
if current == 3:
for l in arr[::-1]:
print(*l[::-1], sep="")
return
# 90도 오른쪽으로 돌린다.
tmp = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
tmp[j][N-1-i] = arr[i][j]
arr = tmp
if current == 0:
for l in arr:
print(*l, sep="")
return
if current == 2:
for l in arr[::-1]:
print(*l[::-1], sep="")
return
solve()
시간초과가 나와버렸다.
공이 있을 수 있는 위치는 모서리와 벽의 주변만이라는 점을 생각해보면, 해당하는 위치들에 대해 미리 연산을 해두는 방식도 가능할 것으로 보여 개선한 후 다시 제출하였다
최종 코드
import sys
input = sys.stdin.readline
print = sys.stdout.write
WALL = 'X'
BALL = 'L'
SPACE = '.'
name = ['오른','아래','왼','위']
D4 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def solve():
N, K = map(int, input().split())
arr = [[*input().rstrip()] for _ in range(N)]
cmds = [input()[0] for _ in range(K)]
DP = [[[None for _ in range(N)] for _ in range(N)] for _ in range(4)]
# 처음 공의 위치를 찾는다
ball = []
for i, l in enumerate(arr):
for j, e in enumerate(l):
if e == BALL:
ball[:2] = i, j
arr[i][j] = SPACE
break
else:
continue
break
# 명령대로 회전시키고 중력을 적용한다
current = 1
for cmd in cmds:
if cmd == "D":
current -= 1
if current < 0:
current = 3
elif cmd == "L":
current += 1
if current > 3:
current = 0
i, j = ball
# 이미 연산한 결과가 있다면 사용
if DP[current][i][j]:
ball = DP[current][i][j]
continue
# 중력 적용
while True:
ni, nj = ball[0] + D4[current][0], ball[1] + D4[current][1]
if not 0 <= ni < N or not 0 <= nj < N:
break
if arr[ni][nj] == WALL:
break
ball = [ni, nj]
DP[current][i][j] = ball
# 결과를 출력한다.
arr[ball[0]][ball[1]] = BALL
if current == 1:
for l in arr:
print("".join(l))
print("\n")
return
if current == 3:
for l in arr[::-1]:
print("".join(l[::-1]))
print("\n")
return
# 90도 오른쪽으로 돌린다.
tmp = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
tmp[j][N - 1 - i] = arr[i][j]
arr = tmp
if current == 0:
for l in arr:
print("".join(l))
print("\n")
return
if current == 2:
for l in arr[::-1]:
print("".join(l[::-1]))
print("\n")
return
solve()DP에 추가적으로 print함수도 sys.stdout.write로 대체해 출력하였고 AC를 받아냈다.
후기
BOJ 13460 : 구슬 탈출 2와 유사해 비교적 쉽게 풀었다.
