[Samsung] 2022-1 오전 1번 술래잡기

April 1, 2023

[Samsung] 2022-1 오전 1번 술래잡기

Question

Language: Python

Difficulty: Gold 1

해당 문제는 주어진 문제의 시뮬레이션을 구현하는 문제이다.

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

도망자의 이동
술래의 이동
도망자 잡기

구체적인 각각의 과정을 살펴보자

도망자의 이동

술래와의 거리가 3이하인 도망자에 대해서만 이동을 수행한다.new_runner_map 이라는 맵에 저장하고 이후에 모든 변경사항을 반영한다.

def move_runners(runner_map,catched,catcher_row,catcher_col):
    new_runner_map=[[[] for _ in range(n)] for _ in range(n)]

    for index in range(m):

        #이미 잡힌 경우
        if catched[index]:
            continue
    
        row,col,dir=runners[index]
        #술레와의 거리가 3보다 큰 경우 이동하지 않는다.
        if (abs(catcher_row-row)+abs(catcher_col-col)) >3:
            new_runner_map[row][col].append(index)
            continue
        
        next_row=row+dy[dir]
        next_col=col+dx[dir]
        next_dir=dir
        #도망자의 다음 위치가 격자 밖인 경우인 경우 반대방향으로 한칸 이동한다.
        if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n :
            next_dir=(dir+2)%4
            next_row=row+dy[next_dir]
            next_col=col+dx[next_dir]

        #만약 다음칸에 술레가 있는 경우에는 움직이지 않는다.
        if (next_row,next_col) == (catcher_row,catcher_col):
            next_row=row
            next_col=col
        
        runners[index]=[next_row,next_col,next_dir]
        new_runner_map[next_row][next_col].append(index)
        
    #새로운 위치 반영
    for row in range(n):
        for col in range(n):
            runner_map[row][col]=new_runner_map[row][col][:]
    
    return runner_map

술래의 이동

우선, 술래의 이동을 수행하기전에 술래가 다음에 이동해야할 방향의 정보를 구하도록 하자 ↑,→,↓,↓,←,←,↑,↑,↑,→,→,→ 와 같은 규칙성을 보인다.

이러한 규칙성을 토대로 이동 방향을 정의해보면 아래와 같다. 정중앙 -> 0,0에 도달한 이후에는 다시 정중앙으로 가기 때문에 지나온 방향에 대한 역순으로 다시 추가해주도록 하여 하나의 방향 주기 만큼의 배열을 정의한다.

#술레에 대한 이동 방향을 기록한 배열 구하기
def get_cather_directions():
    count=0
    directions=[]
    
    #0,0으로 이동하는 이동
    dir_groups=[[0,1],[2,3]]
    for i in range(1,n):
        for dir in dir_groups[i%2==0]:
            directions.extend([dir]*i)
    
    directions.extend([0]*(n-1))


    #중앙으로 되돌아가는 이동
    reversed_directions=directions[::-1]
    for dir in reversed_directions:
        directions.append((dir+2)%4)

    return directions

위의 방향 리스트를 정의하고 나면은 술래의 이동은 다음 방향에 따라 이동만 수행해주면 된다. 만일 1주기([n//2,n//2] -> [0,0] -> [n//2,n//2])을 지나오게 되면 다시 처음부터 진행하면 된다.

def move_catcher(catcher_directions,catcher_direction_index,catcher_row,catcher_col,catcher_dir):
    dir=catcher_directions[catcher_direction_index]
    
    next_catcher_row=catcher_row+dy[dir]
    next_catcher_col=catcher_col+dx[dir]

    #술레가 다음에 바라 보고 있는 방향
    next_catcher_direction_index=catcher_direction_index +1 if catcher_direction_index +1 < (2*(n**2 -1)) else 0
    next_catcher_dir=catcher_directions[next_catcher_direction_index]

    return next_catcher_direction_index,next_catcher_row,next_catcher_col,next_catcher_dir

도망자 잡기

술래는 해당 자리에서 본인 바라보고 있는 방향으로 3칸까지를 검사해서 해당 자리에 도망자가 있는지를 확인한다.

def catch_runners(runner_map,catched,catcher_row,catcher_col,catcher_dir):
    catch_count=0

    for i in range(0,3):
        next_row=catcher_row+dy[catcher_dir]*i
        next_col=catcher_col+dx[catcher_dir]*i
        #범위를 벗어나는 경우
        if next_row < 0 or next_row>=n or next_col <0 or next_col>=n:
            break

        #나무가 있는 경우 무시한다.
        if tree_map[next_row][next_col]!=-1:
            continue

        #도망자를 잡은 경우
        length=len(runner_map[next_row][next_col])
        if length !=0:
            for runner in runner_map[next_row][next_col]:
                catched[runner]=True
            runner_map[next_row][next_col]=[]
            catch_count+=length
    return catch_count

Solution

#술레에 대한 이동 방향을 기록한 배열 구하기
def get_cather_directions():
    count=0
    directions=[]
    
    #0,0으로 이동하는 이동
    dir_groups=[[0,1],[2,3]]
    for i in range(1,n):
        for dir in dir_groups[i%2==0]:
            directions.extend([dir]*i)
    
    directions.extend([0]*(n-1))


    #중앙으로 되돌아가는 이동
    reversed_directions=directions[::-1]
    for dir in reversed_directions:
        directions.append((dir+2)%4)

    return directions

def move_runners(runner_map,catched,catcher_row,catcher_col):
    new_runner_map=[[[] for _ in range(n)] for _ in range(n)]

    for index in range(m):

        #이미 잡힌 경우
        if catched[index]:
            continue
    
        row,col,dir=runners[index]
        #술레와의 거리가 3보다 큰 경우 이동하지 않는다.
        if (abs(catcher_row-row)+abs(catcher_col-col)) >3:
            new_runner_map[row][col].append(index)
            continue
        
        next_row=row+dy[dir]
        next_col=col+dx[dir]
        next_dir=dir

        #도망자의 다음 위치가 격자 밖인 경우인 경우 반대방향으로 한칸 이동한다.
        if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n :
            next_dir=(dir+2)%4
            next_row=row+dy[next_dir]
            next_col=col+dx[next_dir]

        #만약 다음칸에 술레가 있는 경우에는 움직이지 않는다.
        if (next_row,next_col) == (catcher_row,catcher_col):
            next_row=row
            next_col=col
        
        runners[index]=[next_row,next_col,next_dir]
        new_runner_map[next_row][next_col].append(index)
        
    #새로운 위치 반영
    for row in range(n):
        for col in range(n):
            runner_map[row][col]=new_runner_map[row][col][:]
    
    return runner_map
    
#술레의 이동
def move_catcher(catcher_directions,catcher_direction_index,catcher_row,catcher_col,catcher_dir):
    dir=catcher_directions[catcher_direction_index]
    
    next_catcher_row=catcher_row+dy[dir]
    next_catcher_col=catcher_col+dx[dir]

    #술레가 다음에 바라 보고 있는 방향
    next_catcher_direction_index=catcher_direction_index +1 if catcher_direction_index +1 < (2*(n**2 -1)) else 0
    next_catcher_dir=catcher_directions[next_catcher_direction_index]

    return next_catcher_direction_index,next_catcher_row,next_catcher_col,next_catcher_dir

#도망자를 찾는다.
def catch_runners(runner_map,catched,catcher_row,catcher_col,catcher_dir):
    catch_count=0

    for i in range(0,3):
        next_row=catcher_row+dy[catcher_dir]*i
        next_col=catcher_col+dx[catcher_dir]*i
        #범위를 벗어나는 경우
        if next_row < 0 or next_row>=n or next_col <0 or next_col>=n:
            break       

        #나무가 있는 경우 무시한다.
        if tree_map[next_row][next_col]!=-1:
            continue
            
        #도망자를 잡은 경우
        length=len(runner_map[next_row][next_col])
        if length !=0:
            for runner in runner_map[next_row][next_col]:
                catched[runner]=True
            runner_map[next_row][next_col]=[]
            catch_count+=length
    return catch_count

def solution():
    #술레의 이동경로
    catcher_directions=get_cather_directions()
    catcher_direction_index=0

    runner_map=[[[] for _ in range(n)] for _ in range(n)]
    catched=[False]*m

    #맵에서 도망자가 있는 좌표 기록
    for index in range(m):
        row,col,_=runners[index]
        runner_map[row][col].append(index)
    #술레의 좌표
    catcher_row,catcher_col,catcher_dir=n//2,n//2,0

    total_points=0

    for i in range(1,k+1):

        move_runners(runner_map,catched,catcher_row,catcher_col)

        catcher_direction_index,catcher_row,catcher_col,catcher_dir=move_catcher(catcher_directions,catcher_direction_index,catcher_row,catcher_col,catcher_dir)    

        total_points+=(catch_runners(runner_map,catched,catcher_row,catcher_col,catcher_dir)*i)

    print(total_points)



if __name__ == "__main__":
    n,m,h,k=map(int,input().split())
    #row,col,dir (dir==1 좌우 이동, dir ==2 상하 이동)
    runners=[]
    for _ in range(m):
        row,col,dir=map(int,input().split())
        runners.append([row-1,col-1,dir])
    tree_map=[[-1] *n for _ in range(n)]
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    #나무 위치 표시
    for _ in range(h):
        row,col=map(int,input().split())
        tree_map[row-1][col-1]=1
    
    solution()

Twitter Facebook LinkedIn

Jehyun Jung

[Samsung] 2022-1 오전 1번 술래잡기

[Samsung] 2022-1 오전 1번 술래잡기

Question

Language: Python

Difficulty: Gold 1

Solution

공유하기

댓글남기기

참고

Typescript Module Issue

Changing Java Version in Linux

[BOJ] Q1725 히스토그램

[Programmers] Q176962 과제 진행하기