삼성 기출 문제이다.
구현은 내가 가장 좋아하는 유형이어서 재밌게 풀긴했는데 디버깅에서 좀 숨 막혔다..
제출코드
python
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
color = [list(map(int, input().split())) for _ in range(N)]
board = [[0] * N for _ in range(N)]
pawns = [-1] # i번 폰의 위치 정보
dirInfo = [-1] # 방향 정보
for num in range(1, K+1):
i, j, d = map(int, input().split())
pawns.append((i-1, j-1))
dirInfo.append(d-1)
board[i-1][j-1] = num
delta = [(0,1), (0,-1), (-1,0), (1,0)]
bottom = [0] * (K+1) # i번 폰 밑에 있는 말번호
top = [0] * (K+1) # i번 폰 위에 있는 말 번호
def isRange(i, j): # 블루인 경우도 포함
if 0 <= i < N and 0 <= j < N :
if color[i][j] == 2:
return False
return True
return False
def findAll(i): # i번 말 위에 있는 모든 말 찾기
lst = [i]
while 1:
if top[i] == 0:
return lst
lst.append(top[i])
i = top[i]
def findTop(num): # num번 말의 가장 위에 있는 말 찾기
while 1:
if top[num] == 0:
return num
num = top[num]
def findBottom(num): # num번 말의 가장 밑에 있는 말 찾기
while 1:
if bottom[num] == 0:
return num
num = bottom[num]
def white(i, j, d, num): # (i, j)에 num번 말이 이동
bn = bottom[num]
top[bn] = 0 # 난 간다 ㅂㅂ
if board[i][j] == 0: # 아무도 없는 경우
bottom[num] = 0 # 내 밑에는 아무도 없음
board[i][j] = num
pawns[num] = (i, j)
return
# 움직이는 위치에 말이 있는 경우
topPawn = findTop(board[i][j]) # 가장 위에 있는 말 위로 감
top[topPawn] = num
bottom[num] = topPawn
def red(i, j, d, num): # 말 순서 변경
bn = bottom[num]
top[bn] = 0 # 난 간다 ㅂㅂ
# 위 아래 전환
lst = findAll(num)
for idx in range(len(lst)-1):
# idx 밑에 idx+1 이 와야함
bottom[lst[idx]] = lst[idx+1]
top[lst[idx+1]] = lst[idx]
top[lst[0]] = 0
bottom[lst[-1]] = 0
num = lst[-1] # 움직이는 말 변경
# 그리고 이동
white(i, j, d, num)
def blue(i, j, d, num): # i, j 움직이지 않은 위치로 받음
# 방향 반대 0 <-> 1 // 2 <-> 3
if d <= 1:
d = (d+1) % 2
else:
d = (d-1) % 2 + 2
dirInfo[num] = d # 바뀐정보 저장
# i, j에서 1번 이동
di, dj = i+delta[d][0], j+delta[d][1]
if isRange(di, dj) == False: # 못움직이는 경우
if board[i][j] == 0:
board[i][j] = num
return
# 움직이는 경우
if color[di][dj] == 0: # 흰색
white(di, dj, d, num)
elif color[di][dj] == 1: # 빨강
red(di, dj, d, num)
turnCnt = 0
flag = True
while turnCnt <= 1000 and flag == True:
turnCnt += 1
# 1번 말부터 순서대로 이동
for num in range(1, K+1):
bn = findBottom(num)
i, j, d = pawns[bn][0], pawns[bn][1], dirInfo[num]
di, dj = i+delta[d][0], j+delta[d][1]
if board[i][j] == num: # num 이 맨 아랫말이면 board값 수정
board[i][j] = 0
if isRange(di, dj) == False: # 범위 밖인경우 or 블루 인경우
blue(i, j, d, num)
elif color[di][dj] == 0: # 흰색
white(di, dj, d, num)
elif color[di][dj] == 1: # 빨강
red(di, dj, d, num)
bn = findBottom(num)
if len(findAll(bn)) >= 4:
flag = False
break
if turnCnt > 1000:
turnCnt = -1
print(turnCnt)접근방법
color
단순히 보드판의 색을 저장해 놓은 2차원 배열이다.
board
보드에 가장 밑에 있는 장기말의 번호를 저장한다.
여러개가 쌓인 경우에도 가장 밑에있는 말 번호만 저장한다.
pawns
말의 위치 정보를 인덱스 번호에 매칭하여 저장한다.
단, 가장 밑에 있는 말의 번호가 아닌 경우에는 갱신하지 않는다.
즉, board에 있는 번호이어야만 pawns의 정보에 신뢰성이 생긴다.
dirInfo
말의 방향 정보를 저장한다. 방향정보는 delta의 인덱스와 매칭된다.
bottom/top
idx번호의 말 바로 아래/위에 있는 말을 저장한다.
idx번호의 말 바로 아래/위에 말이 없다면 0을 저장한다.
isRange(i, j)
처음에는 배열을 벗어난 경우를 체크하기 위해 만들었지만 파랑색칸의 경우와 로직이 같아서 파랑색 경우도 함께 추가했다.
(i, j)가 배열을 벗어나거나 파랑색 칸이라면 False를 그외에는 True 를 리턴한다.
findAll(num)
num번호를 포함하여 위에 쌓여있는 말들을 리스트 형태로 리턴한다. 빨강색칸의 상하반전 처리를 위해 만들었다.
findTop(num)
num번호 위에 쌓여 말들에서 가장 맨 위에 있는 말의 번호를 리턴한다.
위에 쌓여있는 말이 없다면 num이 리턴된다.
findBottom(num)
findTop(num)과 같다. 맨 아래있는 말의 번호를 리턴한다.
white, red, blue
각 칸 색에서 처리되는 로직을 실행한다.
뚝딱뚝딱