문제
nxn 맵, 각 보드는 빈 공간, 블랙홀, 블록, 웜홀 존재
핀볼은 상하좌우 이동, 규칙에 따라서 움직인다.
1. 블록을 만나면 블록의 모양에 따라 진행 방향 변경
2. 벽을 만나뎜 반대 방햐응로
3. 웜홀을 만나면 다른 웜홀로 이동, 진행 방향 유지
4. 핀볼이 블랙홀을 만나면 게임 종료
게임은 핀볼이 블랙홀을 만나거나, 시작위치로 돌아오면 끝
내 코드
import sys
from collections import defaultdict, deque
sys.stdin = open("input.txt", "rt")
# 핀볼 게임
# nxn 보드, 정사각형 블록, 4가지 삼각형 블록, 웜홀, 블랙홀 존재
# 핀볼은 상하좌우로 이동
# 1. 핀볼이 블록을 만났을 때
# 블록의 수평면이나 수직면 만나면 방향 반대로 진행, 경사면 만나면 직각으로 진행 방향 꺾어서 진행
# 2. 핀볼이 벽을 만날 경우 반대 방향으로 돌아온다.
# 3. 핀볼이 웜홀을 만났을 때 -> 다른 반대편 웜홀로 빠져 나오게 되며, 진행방향은 그대로 유지
# 4. 핀볼이 블랙홀 만났을 때, 게임 끝
# 블랙홀 : -1, 빈공간 : 0, 1~5 블록, 6~10 웜홀
# 종료조건 : 핀볼이 출발위치로 돌아오거나, 블랙홀에 빠질 때 끝. 점수는 벽이나 블록에 부딪힌 횟수
# 얻을 수 있는 점수의 최댓값 구하기
# 1. 빈공간에서 게임 시작. 진행 방향 임의로 선정 가능.
# 2. 시작위치 및 진행 방향 선정했다면 해당 방향으로 이동
# 3. 이동하면서, 블록, 웜홀, 블랙홀 만날 때를 각각 생각하면서 카운트 진행
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def isInner(x,y):
if 0<=x<n and 0<=y<n:
return True
return False
def 핀볼게임(startX,startY,dir):
x,y,d = startX,startY,dir
cnt = 0 # 현재 시작위치 및 시작방향에서의 점수
while True:
x += dx[d]
y += dy[d]
if not isInner(x,y): # 벽 부딪힌 경우
d = (d+2)%4 # 방향 전환
cnt += 1
continue
# 벽 부딪히고 바로 돌아가면 안돼 이후 과정을 수행해야만 함.
if (x, y) == (startX, startY) or g[x][y] == -1: # 시작위치 or 블랙홀 -> 종료조건 검사는 중간에 해야하는가 ?
return cnt
if 1<=g[x][y]<=5: # 블록 만난 경우
d = 블록만남(d, g[x][y])
cnt += 1
elif 6<=g[x][y]<=10: # 웜홀 만난 경우 -> 방향은 유지.
holeA = 웜홀[g[x][y]][0]
holeB = 웜홀[g[x][y]][1]
if (x,y) == (holeA[0],holeA[1]): # 반대방향으로 나가야함
x = holeB[0]
y = holeB[1]
else:
x = holeA[0]
y = holeA[1]
def 블록만남(dir,block_num): # 현재 진행방향에 따라서 블록 처리
if block_num == 1:
if dir == 0: dir = 2
elif dir == 1: dir = 3
elif dir == 2: dir = 1
elif dir == 3: dir = 0
elif block_num == 2:
if dir == 0: dir = 1
elif dir == 1: dir = 3
elif dir == 2: dir = 0
elif dir == 3: dir = 2
elif block_num == 3:
if dir == 0: dir = 3
elif dir == 1: dir = 2
elif dir == 2: dir = 0
elif dir == 3: dir = 1
elif block_num == 4:
if dir == 0: dir = 2
elif dir == 1: dir = 0
elif dir == 2: dir = 3
elif dir == 3: dir = 1
elif block_num == 5:
dir = (dir + 2) % 4
return dir
# def 블록만남(direction, num): # 현재 블록번호와, 현재 방향
# if num == 1:
# if direction == 2: direction = 1
# elif direction == 3: direction = 0
# else: direction = (direction + 2) % 4
# elif num == 2:
# if direction == 0: direction = 1
# elif direction == 3: direction = 2
# else: direction = (direction + 2) % 4
# elif num == 3:
# if direction == 0: direction = 3
# elif direction == 1: direction = 2
# else: direction = (direction + 2) % 4
# elif num == 4:
# if direction == 1: direction = 0
# elif direction == 2: direction = 3
# else: direction = (direction + 2) % 4
# else:
# direction = (direction + 2) % 4
# return direction
T = int(input())
for t in range(1,T+1):
n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
웜홀 = defaultdict(list)
시작위치 = deque()
for i in range(n):
for j in range(n):
if g[i][j] == 0: # 시작위치 가능
시작위치.append((i,j))
if 6<=g[i][j]<=10: # 웜홀
웜홀[g[i][j]].append((i,j)) # key를 웜홀 번호로 해서 저장
res = 0
for x,y in 시작위치:
for dir in range(4):
cnt = 핀볼게임(x,y,dir)
res = max(res, cnt)
print(f"#{t} {res}")코멘트
처음에 해당 문제 시간복잡도를 계산할 때 시간초과가 나는 것은 아닐까 생각을 했었다. 왜냐하면, 시작위치와 시작 방향을 임의로 설정할 수 있다.
-> 시작위치 최대로 nn, 여기서 각 위치마다 방향을 설정할 수 있으므로 (nn)^4으로 생각했다. 하지만, 4승이 아닌 4*(n^2)인 이유는 시작위치에서 4개의 방향을 독립적으로 선택하기 때문이다.
4승을 생각한 이유는, 각 빈공간에서 시작할 때 4가지 방향을 선택할 수 있기 때문에 선택한 것인데.. 하지만 실제로는 각 빈공 간에서 4가지 방향을 독립적으로 선택(영향을 끼치지 않음)할 수 있기 때문에 전체 경우의 수는 4승이 아닌 곱하기로 계산해야 한다.
여기까지가 이제 핀볼의 시작위치 및 시작방향 세팅까지의 시간복잡도,
핀볼 게임에서는 이제 함수 내부에서 핀볼이 이동하는 것이 최대 N^2이므로
최대 O(N^2) * O(N^2) 이므로 O(N^4)이다.
def 핀볼게임(startX, startY, dir):
x, y, d = startX, startY, dir
cnt = 0
while True:
x += dx[d]
y += dy[d]
if not isInner(x, y): # 벽 만난 경우
d = (d + 2) % 4
cnt += 1
continue
if (x, y) == (startX, startY) or g[x][y] == -1: # 시작 위치 or 블랙홀
return cnt
if 1 <= g[x][y] <= 5: # 블록 만난 경우
d = 블록만남(d, g[x][y])
cnt += 1
elif 6 <= g[x][y] <= 10: # 웜홀 만난 경우
holeA = 웜홀[g[x][y]][0]
holeB = 웜홀[g[x][y]][1]
if (x, y) == (holeA[0], holeA[1]):
x, y = holeB[0], holeB[1]
else:
x, y = holeA[0], holeA[1]핀볼 함수
현재 위치 (x, y)와 방향 d를 업데이트하면서 핀볼을 이동시킵니다.
벽을 만나면 방향을 반대로 바꾸고 카운트를 증가시킵니다.
시작 위치로 돌아오거나 블랙홀을 만나면 게임을 종료하고 카운트를 반환합니다.
블록을 만나면 블록만남 함수를 호출하여 새로운 방향을 얻고 카운트를 증가시킵니다.
웜홀을 만나면 반대편 웜홀의 위치로 이동합니다.
블록 처리 함수
def 블록만남(dir, block_num):
if block_num == 1:
if dir == 0:
dir = 2
elif dir == 1:
dir = 3
elif dir == 2:
dir = 1
elif dir == 3:
dir = 0
elif block_num == 2:
if dir == 0:
dir = 1
elif dir == 1:
dir = 3
elif dir == 2:
dir = 0
elif dir == 3:
dir = 2
# ... (block_num 3, 4에 대한 처리)
elif block_num == 5:
dir = (dir + 2) % 4
return dir모의 A형 빡구현.
핀볼 게임 문제를 풀면서 시뮬 + 완탐 방식으로 문제 해결.
모든 가능한 경우를 고려하여 최대 점수를 찾는 것이 핵심이었다.
코드 작성 시 문제에서 주어진 조건을 꼼꼼히 확인하고, 각 상황에 맞는 처리를 해주는 것이 중요하다.
