[Samsung] 2022-1 오후 1번 꼬리잡기 놀이
[Samsung] 2022-1 오후 1번 꼬리잡기 놀이
Question
Language: Python
Difficulty: Gold 1
해당 문제는 주어진 문제의 시뮬레이션을 구현하는 문제이며 dfs가 활용된다.
시뮬레이션 과정은 아래와 같다.
- 사람의 이동
- 공 발사
- 맞은 사람이 있는 경우 점수 획득 및 팀의 이동방향 반전
우선, 위의 시뮬레이션 과정을 진행하기 전에 각 팀의 이동경로, 팀 멤버 정보, 각 멤버에 대한 정보를 구해야한다.
head
각 팀에 대한 정보를 저장하기 위해 팀별 머리사람을 저장한다. 맵 전체를 훑으면서 해당 좌표에 사람이 있는 경우 person_map에 각 사람의 index을 저장하고, people 배열에 각 사람의 row,col,team_index,order을 저장한다.
def find_heads(board,person_map,people):
heads=[]
person_count=0
for row in range(n):
for col in range(n):
temp=board[row][col]
if temp in [1,2,3]:
people.append([row,col,0,0])
person_map[row][col]=person_count
#각 팀의 머리사람에 해당하는 정보
if temp ==1:
heads.append(person_count)
#다음 사람에 대한 진행
person_count+=1
return heads
경로 탐색 및 멤버 설정
각 팀에 대한 이동 경로를 저장하기 위해 각 좌표에 대해 다음 좌표에 대한 정보를 저장한다. 이때, 정방향, 역방향에 해당하는 좌표를 모두 저장하여 이후, 팀의 방향이 반전되었을 때 다음 좌표를 찾기 쉽도록 한다.
0은 역방향에 해당하는 다음 좌표를, 1은 정방향에 해당하는 다음 좌표를 저장한다.
routes[next_row][next_col][1]=[start_row,start_col]
routes[start_row][start_col][0]=[next_row,next_col]
dfs을 통해 이동경로를 구하는데, 이때 머리사람에서 꼬리사람의 방향으로 이동할 수 있도록 초기 방향을 설정한다. dfs을 통해 이동경로를 순환하면서 각 좌표에 대해 위와 같이 연결을 수행하고 이동경로 내에 있는 사람이 있는 경우 각각의 팀에 저장하도록 한다.
def find_teamroute_and_teammember(board,person_map,routes,team_members,people):
heads=find_heads(board,person_map,people)
for team_index in range(m):
head=heads[team_index]
start_row,start_col,_,_=people[head]
row,col,dir=start_row,start_col,0
#시작점에서 다음 방향을 찾기 위해 인접 좌표를 조사한다.
for next_dir in range(4):
next_row=start_row+dy[next_dir]
next_col=start_col+dx[next_dir]
#범위를 벗어나는 경우
if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
continue
#머리사람의 방향이 맞는 경우
if board[next_row][next_col]== 2:
row,col,dir=next_row,next_col,next_dir
routes[next_row][next_col][1]=[start_row,start_col]
routes[start_row][start_col][0]=[next_row,next_col]
break
members=[]
#머리사람에 대한 설정
person_id=person_map[start_row][start_col]
members.append(person_id)
people[person_id][2]=team_index
people[person_id][3]=0
order=1
while (row,col) != (start_row,start_col):
#사람이 있는 자리 인경우 해당 자리의 사람의 index 추가, 각 사람에 대한 팀 정보,순서 정보 저장
if board[row][col] ==2 or board[row][col] ==3:
person_id=person_map[row][col]
members.append(person_id)
people[person_id][2]=team_index
people[person_id][3]=order
order+=1
for next_dir in range(4):
next_row=row+dy[next_dir]
next_col=col+dx[next_dir]
#역방향으로 돌아가지 않도록 한다.
if next_dir == (dir +2)%4:
continue
#범위를 벗어나는 경우
if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
continue
#빈 칸인 경우 넘어간다.
if board[next_row][next_col] ==0:
continue
#다음 좌표에 대한 방향 설정
routes[next_row][next_col][1]=[row,col]
routes[row][col][0]=[next_row,next_col]
row,col,dir=next_row,next_col,next_dir
break
team_members.append(members)
시뮬레이션 진행과정
- 사람의 이동
각 팀에 대해 멤버들을 한 칸씩 이동시키는데, 팀별로 움직이는 방향인 direction의 값에 따라 정방향, 역방향으로 이동을 수행한다.
이때, new_person_map을 활용하여 각각의 사람의 위치를 기록하고 이후 person_map에 옮긴다. 이처럼 일괄적으로 처리하지 않으면 꼬리사람과 머리사람이 연결되어 있는 형태의 팀에 대해서 좌표 설정에 문제가 발생할 수 있으므로 유의한다.
def move_people(person_map,routes,team_members,team_directions,people):
new_person_map=[[-1] * n for _ in range(n)]
for team_index in range(m):
members=team_members[team_index]
direction=team_directions[team_index]
for member in members:
#현재 위치 좌표
row,col,team_index,order=people[member]
#다음 위치 좌표
next_row,next_col=routes[row][col][direction]
#해당 사람에 대한 좌표 이동
people[member]=[next_row,next_col,team_index,order]
#각 좌표에 대한 사람을 저장하고 있는 person_map에도 변경사항 반영
new_person_map[next_row][next_col]=member
for row in range(n):
for col in range(n):
person_map[row][col]=new_person_map[row][col]
- 공의 발사
공의 시작 좌표로 부터 공의 방향에 따라 공을 이동시켜서 해당 좌표에 사람이 있으면 사람의 index을 반환하고 없으면 -1을 반환한다.
또한, 다음 라운드를 위해 공의 시작좌표, 방향을 이동시키는 작업을 처리한다. ball_direction은 공의 발사 방향을, round_direction은 공의 시작 좌표의 방향을 의미한다. 각 라운드가 진행될때마다 round_direction에 의해 공의 시작좌표가 이동하게 되며, n번째 round마다 ball_direction,round_direction을 시계 반대 방향으로 이동시킨다.
def shoot_ball(person_map,ball_start_row,ball_start_col,ball_direction,round_direction,round_index):
result=-1
for i in range(n):
ball_row=ball_start_row+dy[ball_direction]*i
ball_col=ball_start_col+dx[ball_direction]*i
result=person_map[ball_row][ball_col]
#만약 해당 자리에 사람이 있는 경우
if result != -1:
break
#n번째 round 마다 round 진행방향과 공의 발사 방향 변경
if round_index % n ==0:
round_direction=(round_direction+1)%4
ball_direction=(ball_direction+1)%4
else:
ball_start_row=ball_start_row+dy[round_direction]
ball_start_col=ball_start_col+dx[round_direction]
#맞은 사람이 있으면 해당 사람의 index를, 없으면 -1 반환
return result,ball_start_row,ball_start_col,ball_direction,round_direction
- 점수 획득 및 팀의 이동방향 반전
만약 공에 맞은 사람이 있는 경우 해당 함수를 실행한다.
공에 맞은 사람이 해당 팀에서 몇 번째 순서에 있는지 파악하기 위해 선두의 order와의 차이를 활용하고 순서에 대한 제곱으로 점수를 구한다. 그런 다음 해당 팀에 대한 이동방향을 반전시키고, member 배열의 순서또한 뒤집어준다.
def earn_points_and_change_direction(team_members,team_directions,people,member):
team_index=people[member][2]
members=team_members[team_index]
#정방향이면 선두는 첫번째, 역방향이면 마지막
head=members[0]
point=(abs(people[member][3]-people[head][3])+1)**2
#방향 전환 수행
team_directions[team_index]=1-team_directions[team_index]
team_members[team_index]=team_members[team_index][::-1]
return point
Solution
from collections import deque
#각 팀의 머리사람 추출
def find_heads(board,person_map,people):
heads=[]
person_count=0
for row in range(n):
for col in range(n):
temp=board[row][col]
if temp in [1,2,3]:
people.append([row,col,0,0])
person_map[row][col]=person_count
#각 팀의 머리사람에 해당하는 정보
if temp ==1:
heads.append(person_count)
#다음 사람에 대한 진행
person_count+=1
return heads
#각 팀에 대한 경로 매핑 및 멤버 저장
def find_teamroute_and_teammember(board,person_map,routes,team_members,people):
heads=find_heads(board,person_map,people)
for team_index in range(m):
head=heads[team_index]
start_row,start_col,_,_=people[head]
row,col,dir=start_row,start_col,0
#시작점에서 다음 방향을 찾기 위해 인접 좌표를 조사한다.
for next_dir in range(4):
next_row=start_row+dy[next_dir]
next_col=start_col+dx[next_dir]
#범위를 벗어나는 경우
if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
continue
#머리사람의 방향이 맞는 경우
if board[next_row][next_col]== 2:
row,col,dir=next_row,next_col,next_dir
routes[next_row][next_col][1]=[start_row,start_col]
routes[start_row][start_col][0]=[next_row,next_col]
break
members=[]
#머리사람에 대한 설정
person_id=person_map[start_row][start_col]
members.append(person_id)
people[person_id][2]=team_index
people[person_id][3]=0
order=1
while (row,col) != (start_row,start_col):
#사람이 있는 자리 인경우 해당 자리의 사람의 index 추가, 각 사람에 대한 팀 정보,순서 정보 저장
if board[row][col] ==2 or board[row][col] ==3:
person_id=person_map[row][col]
members.append(person_id)
people[person_id][2]=team_index
people[person_id][3]=order
order+=1
for next_dir in range(4):
next_row=row+dy[next_dir]
next_col=col+dx[next_dir]
#역방향으로 돌아가지 않도록 한다.
if next_dir == (dir +2)%4:
continue
#범위를 벗어나는 경우
if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
continue
#빈 칸인 경우 넘어간다.
if board[next_row][next_col] ==0:
continue
#다음 좌표에 대한 방향 설정
routes[next_row][next_col][1]=[row,col]
routes[row][col][0]=[next_row,next_col]
row,col,dir=next_row,next_col,next_dir
break
team_members.append(members)
#각 팀에 대해 사람들을 움직이는 함수
def move_people(person_map,routes,team_members,team_directions,people):
new_person_map=[[-1] * n for _ in range(n)]
for team_index in range(m):
members=team_members[team_index]
direction=team_directions[team_index]
for member in members:
#현재 위치 좌표
row,col,team_index,order=people[member]
#다음 위치 좌표
next_row,next_col=routes[row][col][direction]
#해당 사람에 대한 좌표 이동
people[member]=[next_row,next_col,team_index,order]
#각 좌표에 대한 사람을 저장하고 있는 person_map에도 변경사항 반영
new_person_map[next_row][next_col]=member
for row in range(n):
for col in range(n):
person_map[row][col]=new_person_map[row][col]
def shoot_ball(person_map,ball_start_row,ball_start_col,ball_direction,round_direction,round_index):
result=-1
for i in range(n):
ball_row=ball_start_row+dy[ball_direction]*i
ball_col=ball_start_col+dx[ball_direction]*i
result=person_map[ball_row][ball_col]
#만약 해당 자리에 사람이 있는 경우
if result != -1:
break
#n번째 round 마다 round 진행방향과 공의 발사 방향 변경
if round_index % n ==0:
round_direction=(round_direction+1)%4
ball_direction=(ball_direction+1)%4
else:
ball_start_row=ball_start_row+dy[round_direction]
ball_start_col=ball_start_col+dx[round_direction]
#맞은 사람이 있으면 해당 사람의 index를, 없으면 -1 반환
return result,ball_start_row,ball_start_col,ball_direction,round_direction
#맞은 사람이 있는 팀에 대해 점수를 얻고 방향을 전환한다.
def earn_points_and_change_direction(team_members,team_directions,people,member):
team_index=people[member][2]
members=team_members[team_index]
#정방향이면 선두는 첫번째, 역방향이면 마지막
head=members[0]
point=(abs(people[member][3]-people[head][3])+1)**2
#방향 전환 수행
team_directions[team_index]=1-team_directions[team_index]
team_members[team_index]=team_members[team_index][::-1]
return point
def print_board(board):
for row in board:
print(*row)
def solution():
#모든 사람에 대한 좌표 정보, 팀 정보, 팀에서의 순서정보 기록
people=[]
#각 팀에 대한 팀 정보 기록
team_members=[]
#각 팀의 이동방향 기록 0:역방향, 1:정방향
team_directions=[1] * m
#각 좌표에 대한 사람의 인덱스 정보 저장
person_map=[[-1] * n for _ in range(n)]
#각 좌표에 대해 방향 기록
routes=[[[[-1,-1],[-1,-1]] for _ in range(n)] for _ in range(n)]
#공의 발사 방향
ball_direction=0
#라운드 진행방향
round_direction=3
#공이 발사되는 좌표
ball_start_row,ball_start_col=0,0
#총점
sum_of_points=0
#각 팀에 대한 경로 찾기 및 팀 멤버 세팅
find_teamroute_and_teammember(board,person_map,routes,team_members,people)
for i in range(1,k+1):
#사람을 한 칸 씩 이동
move_people(person_map,routes,team_members,team_directions,people)
#공 발사
member,ball_start_row,ball_start_col,ball_direction,round_direction=shoot_ball(person_map,ball_start_row,ball_start_col,ball_direction,round_direction,i)
if member != -1:
sum_of_points+=earn_points_and_change_direction(team_members,team_directions,people,member)
print(sum_of_points)
if __name__ == "__main__":
n,m,k=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
dy=[0,-1,0,1]
dx=[1,0,-1,0]
solution()
댓글남기기