💯Problem Solving
[BOJ] 2933 미네랄
date
Sep 12, 2023
slug
boj-2933
author
status
Public
tags
Python
BOJ
summary
백준 2933번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Sep 14, 2023 01:56 AM
문제 링크
문제
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.
동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.
창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.
막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.
동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.
문제풀이
막대기는 항상 가로로 1개씩 부시므로 막대기가 배열을 깨는 것을 구현해주고
깰때마다 모든 원소에 대해 bfs를 돌려, cluster들을 찾는다
cluster가 땅에 붙어있지 않는다면, 공중에 뜬 것으로 판단하여 중력을 적용시켜
떨어질떄, 다음 클러스터와 붙거나 땅에 떨어질때까지 반복한다.
이떄 한칸씩 클러스터를 아래로 옮겨주면서 클러스터와 붙거나 땅에 떨어지는지를 판별하면되는데
단순히 y+1이 땅인지, 클러스터인지만 확인해주면 된다.
그리고 배열을 한칸씩 옮길때 순서를 잘 해주어야 반영이 잘된다.
파이썬 문제풀이 코드
from collections import deque R, C = map(int, input().split()) dx = [1, 0, -1, 0] # 동남서북 dy = [0, 1, 0, -1] def bfs(y, x, visited): is_ground = False dq = deque() dq.append((y, x)) trace = [] while dq: y, x = dq.popleft() if y == R-1: # 그라운드에 미네랄이 있다 is_ground = True if visited[y][x] == 1: continue visited[y][x] = 1 # 방문처리 trace.append([y, x]) # 추적 for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= ny < R and 0 <= nx < C: # 조건안에서 if arr[ny][nx] == 'x': # 미네랄이면 dq.append((ny, nx)) # BFS if trace: return is_ground, trace else: return True, [] def process(): visited = [[0] * C for _ in range(R)] # 방문배열 for i in range(R): for j in range(C): if arr[i][j] == 'x': # [print(arr[i]) for i in range(R)] is_ground, trace = bfs(i, j, visited) # [print(arr[i]) for i in range(R)] # print(is_ground, trace) if is_ground == False: # 그라운드에 미네랄이 없다? 중력에 의해 떨어짐 # print("Event") while is_ground == False: for y, x in trace: arr[y][x] = '.' # 빈공간으로 만들고 for y, x in trace: arr[y+1][x] = 'x' # 중력에 의해 떨어짐 # [print(arr[i]) for i in range(R)] # print() trace = [[item[0]+1, item[1]] for item in trace] # trace 갱신 for y, x in trace: if y == R-1: # 땅인경우 is_ground = True break if arr[y+1][x] == 'x' and [y+1, x] not in trace : # 바로 아래 이미 클러스터가 있을 경우, 중복이 아닌경우r is_ground = True # break # visited = [[0] * C for _ in range(R)] # 방문배열 초기화 # is_ground, trace = bfs(i+1, j, visited) # [print(arr[i]) for i in range(R)] return def throw_stick(height, direction): a_h = R-height # arr상 실제 높이 if direction == 0: # 왼쪽 for i in range(C): # 0~C if arr[a_h][i] == 'x': arr[a_h][i] = '.' # 파괴 process() # 합치는 프로세스 break elif direction == 1: # 오른쪽 for i in range(C-1, -1, -1):# C-1 ~ 0 if arr[a_h][i] == 'x': arr[a_h][i] = '.' # 파괴 process() # 합치는 프로세 break arr = [] for _ in range(R): # 환경구축 st = list(input()) arr.append(st) N = int(input()) # 막대기 던진 횟수 direction = 0 # 처음은 0 H_list = list(map(int, input().split())) # 막대 던진 높이 for h in H_list: # print("수행", h) throw_stick(h, direction) direction = 1 - direction # [print(arr[i]) for i in range(R)] [print(''.join(arr[i])) for i in range(R)] # print(direction)
시간복잡도
- ≤ O(*N^4)
입력
첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)
다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.
다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)
마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.
출력
입력 형식과 같은 형식으로 미네랄 모양을 출력한다.
8 8 ........ ........ ...x.xx. ...xxx.. ..xxx... ..x.xxx. ..x...x. .xxx..x. 5 6 6 4 3 1
........ ........ ........ ........ .....x.. ..xxxx.. ..xxx.x. ..xxxxx.