알고리즘 (PS)/BOJ
[백준] 17780 - 새로운 게임 (Python)
에버듀
2024. 5. 29. 10:28
반응형
요구사항에 맞게 구현하면 되는 문제
오랜만에 풀어서 그런지 꽤 어려웠다..
윷놀이 문제처럼 말을 이동하다가 다른 말을 만나면 쌓아야 하는데, 말을 쌓더라도 자신이 갖고있는 방향은 바뀌면 안된다.
class Unit:
def __init__(self, number, row, col, direction):
self.number = number
self.row = row
self.col = col
self.direction = direction
def check_next(self):
if self.direction == RIGHT:
return self.row, self.col + 1
if self.direction == LEFT:
return self.row, self.col - 1
if self.direction == UP:
return self.row - 1, self.col
if self.direction == DOWN:
return self.row + 1, self.col
def change_direction(self):
if self.direction == RIGHT:
self.direction = LEFT
elif self.direction == LEFT:
self.direction = RIGHT
elif self.direction == UP:
self.direction = DOWN
elif self.direction == DOWN:
self.direction = UP
def __str__(self):
return str((self.number, self.row, self.col, self.direction))
먼저 말을 나타내는 Unit 클래스를 작성했다.
말을 쌓을 때는 이 Unit을 직접 쌓음으로서 자신들이 갖고 있는 방향이 유지되도록 하였다.
WHITE, RED, BLUE = 0, 1, 2
RIGHT, LEFT, UP, DOWN = 1, 2, 3, 4
N, K = map(int, input().split())
board_info = [[2 for _ in range(N+2)]] + [[2] + list(map(int, input().split())) + [2] for _ in range(N)] + [[2 for _ in range(N+2)]]
board = [[0 for _ in range(N+2)] for _ in range(N+2)]
unit_info = [[] for _ in range(K + 1)]
for i in range(1, K+1):
row, col, direction = map(int, input().split())
board[row][col] = i
unit_info[i].append(Unit(i, row, col, direction))
보드판 타일색과 이동방향은 상수로 관리해준다.
보드판 바깥으로 나가는 것은 파란색으로 이동하는 것과 같다고 하였으니 보드판 주변을 파란색 타일로 둘러준다.
이렇게하면 1-index로 문제를 풀 수 있고, 이동할 때 범위를 벗어나는 걸 고려하지 않아도 되어서 좋다.
(다른 그래프 문제 풀 때도 애초에 이렇게 설정하고 풀어볼까..)
실제 말의 배치 현황을 나타내는 것은 board로, 각 보드의 타일색 정보는 board_info로 나눠 관리하였다.
unit_info 는 i번째 말 위에 어떤 말들이 쌓여있는지를 나타낸다.
처음에는 자신의 말 위에 자신에 대한 정보만 있도록 세팅하였다.
turn = 0
while turn <= 1000:
turn += 1
for unit_number in range(1, K+1):
if unit_info[unit_number]: # 현재 유닛이 움직일 수 있다면
# 유닛이 보고있는 방향대로 이동
now_unit: Unit = unit_info[unit_number][0]
check_row, check_col = now_unit.check_next()
if board_info[check_row][check_col] == WHITE:
process_white(now_unit, check_row, check_col)
elif board_info[check_row][check_col] == RED:
process_red(now_unit, check_row, check_col)
elif board_info[check_row][check_col] == BLUE:
# 이동한 곳의 판이 파란색인 경우, 방향 바꾸고 파란색이 아니면 이동
now_unit.change_direction()
check_row, check_col = now_unit.check_next()
if board_info[check_row][check_col] != BLUE:
if board_info[check_row][check_col] == WHITE:
process_white(now_unit, check_row, check_col)
elif board_info[check_row][check_col] == RED:
process_red(now_unit, check_row, check_col)
먼저 main 로직은 위와 같이 작성하였다.
현재 유닛이 다른 유닛 위에 올라가 있지 않다면, unit_info 의 자신 번호 데이터가 있다는 의미이다.
이때는 자신이 움직일 수 있다는 의미이므로, 이동하려는 방향의 타일색을 체크한다.
타일색이 하얀색, 빨간색일 때 처리하는 부분은 별도 함수로 분리하였다.
타일색이 파란색일 때, 한번 더 처리해야 하기 때문이다.
def process_white(now_unit, check_row, check_col):
# 기존 말은 보드에서 지우기
board[now_unit.row][now_unit.col] = 0
if board[check_row][check_col] > 0:
# 이동한 곳에 말이 이미 있는 경우, 이동하려는 유닛 위에 기존 말을 쌓기
exist_unit = board[check_row][check_col]
for unit in unit_info[unit_number]:
unit_info[exist_unit].append(unit)
unit.row = check_row
unit.col = check_col
unit_info[unit_number].clear()
# 말이 4개 이상 쌓였다면 게임 종료
if len(unit_info[exist_unit]) >= 4:
print(turn)
exit(0)
else:
# 이동한 곳에 말이 없는 경우, 쌓는 것 없이 이동만
board[check_row][check_col] = now_unit.number
for unit in unit_info[unit_number]:
unit.row = check_row
unit.col = check_col
먼저 하얀색을 처리할 때는 간단하다.
이동하려는 곳에 말이 있다면 현재 자신에게 쌓여있는 말들을 차례대로 순회하면서 이동하려는 말 위에 쌓아준다.
이때 말이 4개 이상 쌓였다면 그대로 턴을 출력하고 프로그램을 종료한다.
만약 이동하려는 곳에 말이 없다면 자신에게 쌓여있는 말 전체의 위치값을 바꿔주고 보드판에 반영하면 된다.
def process_red(now_unit, check_row, check_col):
# 이동한 곳의 판이 빨간색인 경우
board[now_unit.row][now_unit.col] = 0
unit_number = now_unit.number
# 이동한 곳에 말이 있는 경우, 기존 말의 배치를 뒤집고, 이동한 말 위에 추가
if board[check_row][check_col] > 0:
# 이동한 곳에 말이 이미 있는 경우, 이동하려는 유닛 위에 기존 말을 뒤집어서 쌓기
exist_unit = board[check_row][check_col]
while unit_info[unit_number]:
popped_unit: Unit = unit_info[unit_number].pop()
popped_unit.row = check_row
popped_unit.col = check_col
unit_info[exist_unit].append(popped_unit)
# 말이 4개 이상 쌓였다면 게임 종료
if len(unit_info[exist_unit]) >= 4:
print(turn)
exit(0)
else:
# 이동한 곳에 말이 없는 경우, 기존 말의 배치를 뒤집고 이동
inverse_unit_number = unit_info[unit_number][-1].number
if len(unit_info[unit_number]) > 1:
while unit_info[unit_number]:
popped_unit: Unit = unit_info[unit_number].pop()
popped_unit.row = check_row
popped_unit.col = check_col
unit_info[inverse_unit_number].append(popped_unit)
else:
unit_info[unit_number][-1].row = check_row
unit_info[unit_number][-1].col = check_col
board[check_row][check_col] = inverse_unit_number
이동하려는 곳에 말이 있다면 자신의 말을 뒤에서부터 하나씩 빼면서 기존 말 위에 추가해준다.
이렇게하면 역순으로 쌓이게 된다.
이동하려는 곳에 말이 없다면 현재 쌓여있는 것을 반대로 뒤집어주고 위치만 이동한 곳으로 바꿔준다.
위 코드에서 뒤집으려는 말의 개수가 1개보다 큰지 체크하는 이유는 만약 뒤집으려는 말의 개수가 1개라면 반복문이 무한으로 돌기 때문이다.
정답 코드
class Unit:
def __init__(self, number, row, col, direction):
self.number = number
self.row = row
self.col = col
self.direction = direction
def check_next(self):
if self.direction == RIGHT:
return self.row, self.col + 1
if self.direction == LEFT:
return self.row, self.col - 1
if self.direction == UP:
return self.row - 1, self.col
if self.direction == DOWN:
return self.row + 1, self.col
def change_direction(self):
if self.direction == RIGHT:
self.direction = LEFT
elif self.direction == LEFT:
self.direction = RIGHT
elif self.direction == UP:
self.direction = DOWN
elif self.direction == DOWN:
self.direction = UP
def __str__(self):
return str((self.number, self.row, self.col, self.direction))
WHITE, RED, BLUE = 0, 1, 2
RIGHT, LEFT, UP, DOWN = 1, 2, 3, 4
N, K = map(int, input().split())
board_info = [[2 for _ in range(N+2)]] + [[2] + list(map(int, input().split())) + [2] for _ in range(N)] + [[2 for _ in range(N+2)]]
board = [[0 for _ in range(N+2)] for _ in range(N+2)]
unit_info = [[] for _ in range(K + 1)]
for i in range(1, K+1):
row, col, direction = map(int, input().split())
board[row][col] = i
unit_info[i].append(Unit(i, row, col, direction))
def process_white(now_unit, check_row, check_col):
# 기존 말은 보드에서 지우기
board[now_unit.row][now_unit.col] = 0
if board[check_row][check_col] > 0:
# 이동한 곳에 말이 이미 있는 경우, 이동하려는 유닛 위에 기존 말을 쌓기
exist_unit = board[check_row][check_col]
for unit in unit_info[unit_number]:
unit_info[exist_unit].append(unit)
unit.row = check_row
unit.col = check_col
unit_info[unit_number].clear()
# 말이 4개 이상 쌓였다면 게임 종료
if len(unit_info[exist_unit]) >= 4:
print(turn)
exit(0)
else:
# 이동한 곳에 말이 없는 경우, 쌓는 것 없이 이동만
board[check_row][check_col] = now_unit.number
for unit in unit_info[unit_number]:
unit.row = check_row
unit.col = check_col
def process_red(now_unit, check_row, check_col):
# 이동한 곳의 판이 빨간색인 경우
board[now_unit.row][now_unit.col] = 0
unit_number = now_unit.number
# 이동한 곳에 말이 있는 경우, 기존 말의 배치를 뒤집고, 이동한 말 위에 추가
if board[check_row][check_col] > 0:
# 이동한 곳에 말이 이미 있는 경우, 이동하려는 유닛 위에 기존 말을 뒤집어서 쌓기
exist_unit = board[check_row][check_col]
while unit_info[unit_number]:
popped_unit: Unit = unit_info[unit_number].pop()
popped_unit.row = check_row
popped_unit.col = check_col
unit_info[exist_unit].append(popped_unit)
# 말이 4개 이상 쌓였다면 게임 종료
if len(unit_info[exist_unit]) >= 4:
print(turn)
exit(0)
else:
# 이동한 곳에 말이 없는 경우, 기존 말의 배치를 뒤집고 이동
inverse_unit_number = unit_info[unit_number][-1].number
if len(unit_info[unit_number]) > 1:
while unit_info[unit_number]:
popped_unit: Unit = unit_info[unit_number].pop()
popped_unit.row = check_row
popped_unit.col = check_col
unit_info[inverse_unit_number].append(popped_unit)
else:
unit_info[unit_number][-1].row = check_row
unit_info[unit_number][-1].col = check_col
board[check_row][check_col] = inverse_unit_number
turn = 0
while turn <= 1000:
turn += 1
for unit_number in range(1, K+1):
if unit_info[unit_number]: # 현재 유닛이 움직일 수 있다면
# 유닛이 보고있는 방향대로 이동
now_unit: Unit = unit_info[unit_number][0]
check_row, check_col = now_unit.check_next()
if board_info[check_row][check_col] == WHITE:
process_white(now_unit, check_row, check_col)
elif board_info[check_row][check_col] == RED:
process_red(now_unit, check_row, check_col)
elif board_info[check_row][check_col] == BLUE:
# 이동한 곳의 판이 파란색인 경우, 방향 바꾸고 파란색이 아니면 이동
now_unit.change_direction()
check_row, check_col = now_unit.check_next()
if board_info[check_row][check_col] != BLUE:
if board_info[check_row][check_col] == WHITE:
process_white(now_unit, check_row, check_col)
elif board_info[check_row][check_col] == RED:
process_red(now_unit, check_row, check_col)
print(-1)반응형