[Samsung] 2022-1 오후 1번 꼬리잡기 놀이

Question

Language: Python

Difficulty: Gold 1

해당 문제는 주어진 문제의 시뮬레이션을 구현하는 문제이며 dfs가 활용된다.

시뮬레이션 과정은 아래와 같다.

  1. 사람의 이동
  2. 공 발사
  3. 맞은 사람이 있는 경우 점수 획득 및 팀의 이동방향 반전

우선, 위의 시뮬레이션 과정을 진행하기 전에 각 팀의 이동경로, 팀 멤버 정보, 각 멤버에 대한 정보를 구해야한다.

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)

시뮬레이션 진행과정

  1. 사람의 이동

각 팀에 대해 멤버들을 한 칸씩 이동시키는데, 팀별로 움직이는 방향인 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]
  1. 공의 발사

공의 시작 좌표로 부터 공의 방향에 따라 공을 이동시켜서 해당 좌표에 사람이 있으면 사람의 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
  1. 점수 획득 및 팀의 이동방향 반전

만약 공에 맞은 사람이 있는 경우 해당 함수를 실행한다.

공에 맞은 사람이 해당 팀에서 몇 번째 순서에 있는지 파악하기 위해 선두의 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()

댓글남기기