[백준] 20165번 인내의 도미노 장인 호석

park geonwoo·2024년 10월 28일
코딩테스트

코딩테스트

목록 보기
29/32

https://www.acmicpc.net/problem/20165

이번 문제는 도미노를 넘기는 시뮬레이션을 통해 공격수가 총 몇 개의 도미노를 넘겼는지 계산하고, 최종 게임판의 상태를 출력하는 문제입니다. 공격과 수비의 과정을 반복하면서 도미노의 상태를 관리해야 합니다. 효율적이고 간결한 파이썬 코드를 작성하고, 그에 대한 자세한 분석을 제공하겠습니다.

문제 이해

문제 요약

  • 목표:
    • N행 M열의 2차원 격자에 도미노를 세웁니다. 각 도미노는 높이 1 이상 5 이하입니다.
    • R번의 라운드 동안:
      • 공격수는 특정 격자에 있는 도미노를 특정 방향(E, W, S, N)으로 밀어 넘깁니다.
        • 도미노가 넘어지면, 해당 방향으로 최대 K-1개의 도미노가 연쇄적으로 넘어집니다.
        • 이미 넘어져 있는 도미노를 밀면 아무 일도 일어나지 않습니다.
      • 수비수는 넘어져 있는 도미노 중 하나를 다시 세웁니다.
        • 넘어지지 않은 도미노를 세우려 해도 아무 일도 일어나지 않습니다.
    • 각 라운드마다 공격수가 넘긴 도미노의 수를 세고, 총합을 공격수의 점수로 합니다.
  • 출력:
    • 공격수의 총 점수.
    • 최종 게임판 상태: 'F'는 넘어져 있는 도미노, 'S'는 세워져 있는 도미노.

예제 분석

예제 입력 1:

5 5 3
1 1 1 1 1
1 2 2 1 1
3 1 2 2 2
1 3 2 1 1
1 3 3 1 1
3 1 E
3 5
5 3 N
3 3
5 2 N
3 1

예제 출력 1:

11
S F S S S
S F S S S
S F S F S
S F F S S
S F F S S

해석:

  • 초기 도미노 상태와 3번의 라운드를 통해 도미노가 넘어지고 세워지는 과정을 추적하여, 공격수가 총 11개의 도미노를 넘어뜨렸음을 알 수 있습니다.

해결 방법

접근 방식

이 문제는 시뮬레이션을 통해 각 라운드마다 도미노의 상태를 관리하고, 공격수의 점수를 계산하는 방식으로 해결할 수 있습니다. 주요 단계는 다음과 같습니다:

  1. 입력 처리:
    • 게임판의 크기 N, M과 라운드 수 R을 입력받습니다.
    • N개의 행에 걸쳐 M개의 도미노 높이를 입력받습니다.
    • R번의 라운드 동안 공격수와 수비수의 행동을 입력받습니다.
  2. 게임판 상태 관리:
    • 도미노의 상태를 2차원 리스트로 관리합니다.
    • 'F'는 넘어져 있는 상태, 'S'는 세워져 있는 상태로 표시합니다.
  3. 공격 시뮬레이션:
    • 공격수가 도미노를 밀면, 해당 방향으로 도미노가 넘어지며 연쇄 반응을 일으킵니다.
    • BFS(너비 우선 탐색)을 사용하여 도미노의 연쇄 반응을 효율적으로 처리합니다.
  4. 수비 시뮬레이션:
    • 수비수가 특정 도미노를 세우면, 해당 도미노의 상태를 'S'로 변경합니다.
  5. 점수 계산 및 최종 상태 출력:
    • 각 라운드마다 넘어뜨린 도미노의 수를 누적하여 공격수의 점수를 계산합니다.
    • 모든 라운드가 끝난 후, 최종 게임판의 상태를 출력합니다.

알고리즘 단계

  1. 입력 처리:
    • N, M, R을 입력받습니다.
    • N개의 행에 걸쳐 M개의 도미노 높이를 입력받아 2차원 리스트 height에 저장합니다.
    • 초기 도미노 상태를 모두 'S'로 설정한 2차원 리스트 toppled를 만듭니다.
  2. 공격 함수 구현:
    • 특정 위치의 도미노를 특정 방향으로 밀어 넘기는 함수를 구현합니다.
    • BFS를 사용하여 도미노가 넘어지는 과정을 시뮬레이션합니다.
    • 넘어뜨린 도미노의 수를 반환합니다.
  3. 수비 함수 구현:
    • 특정 위치의 도미노를 세우는 함수를 구현합니다.
    • 도미노가 'F'인 경우에만 'S'로 변경합니다.
  4. 라운드 처리:
    • 각 라운드마다 공격과 수비를 순서대로 수행합니다.
    • 공격수의 점수를 누적합니다.
  5. 출력:
    • 공격수의 총 점수를 출력합니다.
    • 최종 게임판의 상태를 'F'와 'S'로 출력합니다.

코드 구현

아래는 위의 접근 방식을 구현한 파이썬 코드입니다.

import sys
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()

    idx = 0
    N = int(data[idx])
    M = int(data[idx+1])
    R = int(data[idx+2])
    idx += 3

    # Read the grid heights
    height = []
    for _ in range(N):
        row = list(map(int, data[idx:idx+M]))
        height.append(row)
        idx += M

    # Initialize toppled status: False = 'S', True = 'F'
    toppled = [[False for _ in range(M)] for _ in range(N)]

    # Direction mappings
    direction_map = {
        'N': (-1, 0),
        'S': (1, 0),
        'E': (0, 1),
        'W': (0, -1)
    }

    total_score = 0

    # Process R rounds
    for _ in range(R):
        # Attack action
        attack_x = int(data[idx]) -1
        attack_y = int(data[idx+1]) -1
        D = data[idx+2]
        idx +=3

        # Perform attack if the domino is standing
        if not toppled[attack_x][attack_y]:
            queue = deque()
            queue.append( (attack_x, attack_y, D) )
            toppled[attack_x][attack_y] = True
            total_score +=1

            while queue:
                x, y, direction = queue.popleft()
                K = height[x][y]
                dx, dy = direction_map[direction]

                for step in range(1, K):
                    nx = x + dx*step
                    ny = y + dy*step
                    if 0 <= nx < N and 0 <= ny < M:
                        if not toppled[nx][ny]:
                            toppled[nx][ny] = True
                            total_score +=1
                            # If the domino has height >1, it can topple further
                            if height[nx][ny] >1:
                                queue.append( (nx, ny, direction) )
                    else:
                        break  # Out of bounds

        # Defense action
        defend_x = int(data[idx]) -1
        defend_y = int(data[idx+1]) -1
        idx +=2

        # Perform defense if the domino is toppled
        if toppled[defend_x][defend_y]:
            toppled[defend_x][defend_y] = False

    # Output
    print(total_score)
    for row in toppled:
        print(' '.join(['F' if cell else 'S' for cell in row]))

if __name__ == "__main__":
    main()

코드 분석

1. 입력 처리

import sys
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()

    idx = 0
    N = int(data[idx])
    M = int(data[idx+1])
    R = int(data[idx+2])
    idx += 3
  • 설명:
    • sys.stdin.read()를 사용하여 전체 입력을 한 번에 읽어옵니다.
    • split()을 통해 입력을 공백 기준으로 분할하여 data 리스트에 저장합니다.
    • idx를 사용하여 입력 데이터의 현재 위치를 추적합니다.
    • 첫 번째, 두 번째, 세 번째 요소를 각각 N(행 수), M(열 수), R(라운드 수)로 변환합니다.

2. 게임판 초기화

    # Read the grid heights
    height = []
    for _ in range(N):
        row = list(map(int, data[idx:idx+M]))
        height.append(row)
        idx += M

    # Initialize toppled status: False = 'S', True = 'F'
    toppled = [[False for _ in range(M)] for _ in range(N)]
  • 설명:
    • N개의 행을 읽어 M개의 도미노 높이를 height 2차원 리스트에 저장합니다.
    • toppled 2차원 리스트를 초기화하여 모든 도미노를 세운 상태('S')로 설정합니다. False는 'S', True는 'F'를 의미합니다.

3. 방향 매핑 정의

    # Direction mappings
    direction_map = {
        'N': (-1, 0),
        'S': (1, 0),
        'E': (0, 1),
        'W': (0, -1)
    }
  • 설명:
    • 'N', 'S', 'E', 'W' 방향을 각각 행과 열의 변화량으로 매핑합니다.
    • 예: 'N'은 위쪽으로 이동하므로 행은 -1, 열은 0.

4. 라운드 처리 및 공격 시뮬레이션

    total_score = 0

    # Process R rounds
    for _ in range(R):
        # Attack action
        attack_x = int(data[idx]) -1
        attack_y = int(data[idx+1]) -1
        D = data[idx+2]
        idx +=3

        # Perform attack if the domino is standing
        if not toppled[attack_x][attack_y]:
            queue = deque()
            queue.append( (attack_x, attack_y, D) )
            toppled[attack_x][attack_y] = True
            total_score +=1

            while queue:
                x, y, direction = queue.popleft()
                K = height[x][y]
                dx, dy = direction_map[direction]

                for step in range(1, K):
                    nx = x + dx*step
                    ny = y + dy*step
                    if 0 <= nx < N and 0 <= ny < M:
                        if not toppled[nx][ny]:
                            toppled[nx][ny] = True
                            total_score +=1
                            # If the domino has height >1, it can topple further
                            if height[nx][ny] >1:
                                queue.append( (nx, ny, direction) )
                    else:
                        break  # Out of bounds
  • 설명:
    • 각 라운드마다 공격수의 행동을 읽습니다: X, Y, D.
      • 입력은 1-based 인덱스이므로, 0-based로 변환 (1).
    • 도미노가 세워져 있는 상태('S')라면 공격을 수행합니다:
      • BFS를 위한 큐에 현재 도미노의 위치와 방향을 추가합니다.
      • 해당 도미노를 'F'로 설정하고, total_score를 1 증가시킵니다.
    • 큐를 이용하여 도미노의 연쇄 반응을 처리합니다:
      • 큐에서 도미노를 하나씩 꺼내어, 해당 도미노의 높이 K만큼 지정된 방향으로 도미노를 넘깁니다.
      • 각 스텝마다 도미노가 세워져 있다면, 'F'로 설정하고 total_score를 증가시킵니다.
      • 넘겨진 도미노의 높이가 2 이상이라면, 다시 큐에 추가하여 추가적인 연쇄 반응을 유발합니다.

5. 수비 시뮬레이션

        # Defense action
        defend_x = int(data[idx]) -1
        defend_y = int(data[idx+1]) -1
        idx +=2

        # Perform defense if the domino is toppled
        if toppled[defend_x][defend_y]:
            toppled[defend_x][defend_y] = False
  • 설명:
    • 각 라운드마다 수비수의 행동을 읽습니다: X, Y.
      • 입력은 1-based 인덱스이므로, 0-based로 변환 (1).
    • 도미노가 넘어져 있는 상태('F')라면, 다시 세웁니다('S').

6. 최종 출력

    # Output
    print(total_score)
    for row in toppled:
        print(' '.join(['F' if cell else 'S' for cell in row]))
  • 설명:
    • 공격수가 넘긴 도미노의 총 수를 출력합니다.
    • 게임판의 최종 상태를 'F'와 'S'로 출력합니다.

시간 복잡도 및 효율성

시간 복잡도

  • 입력 처리: O(N*M + R)
    • N x M 도미노의 높이를 읽고, R 라운드의 공격과 수비를 처리합니다.
  • 공격 시뮬레이션: O(R*K)
    • 각 라운드마다 BFS를 통해 최대 K-1 방향으로 도미노를 넘깁니다.
    • K는 최대 5이므로, 상수 시간으로 간주할 수 있습니다.
  • 전체 시간 복잡도: O(N*M + R)
    • N과 M이 최대 100, R이 최대 10,000이므로, 충분히 빠르게 동작합니다.

공간 복잡도

  • 도미노 높이 저장: O(N*M)
  • 도미노 상태 저장: O(N*M)
  • 큐 사용: O(N*M) (최악의 경우 모든 도미노가 동시에 넘어질 수 있지만, N,M이 작으므로 무시 가능)
  • 전체 공간 복잡도: O(N*M)

알고리즘 및 자료구조 설명

알고리즘: BFS를 이용한 시뮬레이션

  • BFS (너비 우선 탐색):
    • 도미노가 넘어지는 연쇄 반응을 효과적으로 처리하기 위해 BFS를 사용합니다.
    • BFS는 레벨별로 도미노를 처리하여, 도미노가 동시에 넘어지는 경우를 정확하게 반영할 수 있습니다.
  • 연쇄 반응 처리:
    • 특정 도미노를 밀면, 지정된 방향으로 K-1개의 도미노가 넘겨집니다.
    • 넘겨진 도미노가 다시 넘겨질 수 있는 경우, 큐에 추가하여 추가적인 반응을 유도합니다.

자료구조: 2차원 리스트 및 큐

  • 2차원 리스트 (height와 toppled):
    • 게임판의 도미노 높이를 저장하는 height 리스트와 도미노의 현재 상태를 저장하는 toppled 리스트를 사용합니다.
    • 인덱스 접근이 빠르고, 간단하게 도미노의 상태를 업데이트할 수 있습니다.
  • 큐 (deque):
    • BFS를 효율적으로 수행하기 위해 collections.deque를 사용합니다.
    • FIFO 구조로, 도미노의 연쇄 반응을 순차적으로 처리할 수 있습니다.
profile
park geonwoo
이전 포스트

[백준] 12933번 오리

다음 포스트

[프로그래머스] 스킬트리

0개의 댓글