Jehyun Jung

Slowly Developing Myself

[Samsung] 2021-2 오전 1번 정육면체 한번 더 굴리기

Question

Language: Python

Difficulty: Gold 3

해당 문제에서 구현해야될 부분은 크게 2가지이다.

  1. bfs을 통해 component 찾기
  2. 주사위의 회전 구현

각 세부 과정은 아래와 같다

  1. Component 찾기

bfs을 활용하여 인접한 칸에 같은 값을 가지는 좌표끼리 묶어서 component을 구성한다.

def find_components():
    component_index=0
    component_map=[[0] * n for _ in range(n)]
    components=[]
    visited=[[False] * n for _ in range(n)]
    for start_row in range(n):
        for start_col in range(n):
            if not visited[start_row][start_col]:
                queue=deque([(start_row,start_col)])
                value=board[start_row][start_col]
                score=0
                while queue:
                    row,col=queue.popleft()
                    if visited[row][col]:
                        continue
                    visited[row][col]=True
                    #각 좌표가 포함된 component의 index 저장
                    component_map[row][col]=component_index
                    score+=value
                    for dir in range(4):
                        next_row=row+dy[dir]
                        next_col=col+dx[dir]
                        #범위를 벗어나는 경우
                        if next_row < 0 or next_row>=n or next_col< 0 or next_col>=n:
                            continue
                        
                        #인접한 칸이 같은 값을 가지지 않은 경우 component에 포함하지 않는다.
                        if board[next_row][next_col] != value:
                            continue
                        
                        queue.append((next_row,next_col))

                components.append(score)
                component_index+=1
    
    return component_map,components
  1. 주사위의 회전

각 방향에 따라 rows,cols을 변경해주는 작업을 진행한다. 주사위 굴리기과 동일한 방식으로 구현하였다.

#북쪽 이동
if next_dice_dir ==0:
    dice_rows.insert(0,dice_rows.pop())
    dice_cols[1]=dice_rows[1]
#동쪽 이동
elif next_dice_dir ==1:
    dice_cols.append(dice_rows.pop())
    dice_rows.append(dice_cols.pop(0))
    dice_rows[1]=dice_cols[1]
#남쪽 이동
elif next_dice_dir==2:
    dice_rows.append(dice_rows.pop(0))
    dice_cols[1]=dice_rows[1]
#서쪽이동
elif next_dice_dir==3:
    dice_cols.insert(0,dice_rows.pop())
    dice_rows.append(dice_cols.pop())
    dice_rows[1]=dice_cols[1]

위의 2가지 연산만 구현하면 나머지 과정은 어렵지 않게 구현할 수 있다.

Solution

from collections import deque

def find_components():
    component_index=0
    component_map=[[0] * n for _ in range(n)]
    components=[]
    visited=[[False] * n for _ in range(n)]
    for start_row in range(n):
        for start_col in range(n):
            if not visited[start_row][start_col]:
                queue=deque([(start_row,start_col)])
                value=board[start_row][start_col]
                score=0
                while queue:
                    row,col=queue.popleft()
                    if visited[row][col]:
                        continue
                    visited[row][col]=True
                    #각 좌표가 포함된 component의 index 저장
                    component_map[row][col]=component_index
                    score+=value
                    for dir in range(4):
                        next_row=row+dy[dir]
                        next_col=col+dx[dir]
                        #범위를 벗어나는 경우
                        if next_row < 0 or next_row>=n or next_col< 0 or next_col>=n:
                            continue
                        
                        #인접한 칸이 같은 값을 가지지 않은 경우 component에 포함하지 않는다.
                        if board[next_row][next_col] != value:
                            continue
                        
                        queue.append((next_row,next_col))

                components.append(score)
                component_index+=1
    
    return component_map,components

def first_move(dice_row,dice_col,dice_rows,dice_cols):
    next_dice_row=dice_row+dy[1]
    next_dice_col=dice_col+dx[1]

    dice_cols.append(dice_rows.pop())
    dice_rows.append(dice_cols.pop(0))
    dice_rows[1]=dice_cols[1]

    return next_dice_row,next_dice_col

#주사위의 이동 수행
def move_dice(dice_row,dice_col,dice_dir,dice_rows,dice_cols):
    next_dice_dir=dice_dir
    #바닥면에 적혀있는 숫자보다 주사위의 알랫면 숫자가 큰 경우 시계방향 회전
    if board[dice_row][dice_col] < dice_rows[1]:
        next_dice_dir=(dice_dir+1)%4
    #작은 경우에는 반시계 방향 회전
    elif board[dice_row][dice_col] > dice_rows[1]:
        next_dice_dir=(dice_dir-1)%4

    next_dice_row=dice_row+dy[next_dice_dir]
    next_dice_col=dice_col+dx[next_dice_dir]

    #범위를 벗어나는 경우 반대방향으로 한 칸 이동
    if next_dice_row < 0 or next_dice_row>=n or next_dice_col< 0 or next_dice_col>=n:
        next_dice_dir=(next_dice_dir+2)%4
        next_dice_row=dice_row+dy[next_dice_dir]
        next_dice_col=dice_col+dx[next_dice_dir]
    
    #주사위 이동 실행
    #북쪽 이동
    if next_dice_dir ==0:
        dice_rows.insert(0,dice_rows.pop())
        dice_cols[1]=dice_rows[1]
    #동쪽 이동
    elif next_dice_dir ==1:
        dice_cols.append(dice_rows.pop())
        dice_rows.append(dice_cols.pop(0))
        dice_rows[1]=dice_cols[1]
    #남쪽 이동
    elif next_dice_dir==2:
        dice_rows.append(dice_rows.pop(0))
        dice_cols[1]=dice_rows[1]
    #서쪽이동
    elif next_dice_dir==3:
        dice_cols.insert(0,dice_rows.pop())
        dice_rows.append(dice_cols.pop())
        dice_rows[1]=dice_cols[1]
    
    
    return next_dice_row,next_dice_col,next_dice_dir


def solution():
    #모든 컴포넌트를 찾는 과정을 진행한다.
    component_map,components=find_components()

    #초기 주사위 정보 초기화
    dice_row,dice_col,dice_dir=0,0,1
    dice_rows=[5,6,2,1]
    dice_cols=[4,6,3]
    total_score=0

    #처음 이동 수행
    dice_row,dice_col=first_move(dice_row,dice_col,dice_rows,dice_cols)
    total_score+=components[component_map[dice_row][dice_col]]

    for _ in range(1,m):
        
        dice_row,dice_col,dice_dir=move_dice(dice_row,dice_col,dice_dir,dice_rows,dice_cols)
        score=components[component_map[dice_row][dice_col]]
        total_score+=score

    print(total_score)

if __name__ == "__main__":
    n,m=map(int,(input().split()))
    board=[list(map(int,input().split())) for _ in range(n)]


    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    solution()

Solution 2

위에서는 dice_row,dice_col,dice_dir,dice_rows,dice_cols을 분리하였지만 아래와 같이 class로 묶어서 구현할 수 있다.

from collections import deque

class Dice:
    def __init__(self):
        self.row=0
        self.col=0
        self.dir=1
        self.back=5
        self.bottom=6
        self.front=2
        self.top=1
        self.left=4
        self.right=3

        
    def roll_north(self):
        self.back,self.bottom,self.front,self.top=self.top,self.back,self.bottom,self.front
    def roll_south(self):
        self.back,self.bottom,self.front,self.top=self.bottom,self.front,self.top,self.back
    def roll_east(self):
        self.left,self.bottom,self.right,self.top=self.bottom,self.right,self.top,self.left
    def roll_west(self):
        self.left,self.bottom,self.right,self.top=self.top,self.left,self.bottom,self.right


def find_components():
    component_index=0
    component_map=[[0] * n for _ in range(n)]
    components=[]
    visited=[[False] * n for _ in range(n)]
    for start_row in range(n):
        for start_col in range(n):
            if not visited[start_row][start_col]:
                queue=deque([(start_row,start_col)])
                value=board[start_row][start_col]
                score=0
                while queue:
                    row,col=queue.popleft()
                    if visited[row][col]:
                        continue
                    visited[row][col]=True
                    #각 좌표가 포함된 component의 index 저장
                    component_map[row][col]=component_index
                    score+=value
                    for dir in range(4):
                        next_row=row+dy[dir]
                        next_col=col+dx[dir]
                        #범위를 벗어나는 경우
                        if next_row < 0 or next_row>=n or next_col< 0 or next_col>=n:
                            continue
                        
                        #인접한 칸이 같은 값을 가지지 않은 경우 component에 포함하지 않는다.
                        if board[next_row][next_col] != value:
                            continue
                        
                        queue.append((next_row,next_col))

                components.append(score)
                component_index+=1
    
    return component_map,components

def first_move(dice):
    dice.row=dice.row+dy[dice.dir]
    dice.col=dice.col+dx[dice.dir]
    dice.roll_east()

#주사위의 이동 수행
def move_dice(dice):
    dice_row,dice_col,dice_dir=dice.row,dice.col,dice.dir
    next_dice_dir=dice_dir
    #바닥면에 적혀있는 숫자보다 주사위의 알랫면 숫자가 큰 경우 시계방향 회전
    if board[dice_row][dice_col] < dice.bottom:
        next_dice_dir=(dice_dir+1)%4
    #작은 경우에는 반시계 방향 회전
    elif board[dice_row][dice_col] > dice.bottom:
        next_dice_dir=(dice_dir-1)%4

    next_dice_row=dice_row+dy[next_dice_dir]
    next_dice_col=dice_col+dx[next_dice_dir]

    #범위를 벗어나는 경우 반대방향으로 한 칸 이동
    if next_dice_row < 0 or next_dice_row>=n or next_dice_col< 0 or next_dice_col>=n:
        next_dice_dir=(next_dice_dir+2)%4
        next_dice_row=dice_row+dy[next_dice_dir]
        next_dice_col=dice_col+dx[next_dice_dir]

    #북
    if next_dice_dir==0:
        dice.roll_north()
    #동
    elif next_dice_dir==1:
        dice.roll_east()
    #남
    elif next_dice_dir==2:
        dice.roll_south()
    #서
    else:
        dice.roll_west()
    
    #주사위 이동 실행
    dice.row,dice.col,dice.dir=next_dice_row,next_dice_col,next_dice_dir


def solution():
    #모든 컴포넌트를 찾는 과정을 진행한다.
    component_map,components=find_components()

    #초기 주사위 정보 초기화
    dice=Dice()
    total_score=0

    #처음 이동 수행
    first_move(dice)
    total_score+=components[component_map[dice.row][dice.col]]

    for _ in range(1,m):
        
        move_dice(dice)
        score=components[component_map[dice.row][dice.col]]
        total_score+=score

    print(total_score)

if __name__ == "__main__":
    n,m=map(int,(input().split()))
    board=[list(map(int,input().split())) for _ in range(n)]


    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    solution()

댓글남기기

참고