[백준/2933/18500] 미네랄 (Python)

Problem : https://www.acmicpc.net/problem/2933

2933번: 미네랄

 

Problem2 : https://www.acmicpc.net/problem/18500

18500번: 미네랄 2

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:20:04

 

---

 

문제 설명

 

 

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.

동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.

창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.

막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.

미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

 

출력

 

입력 형식과 같은 형식으로 미네랄 모양을 출력한다.

 

입력 예시

 

5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3

 

출력 예시

 

......
......
..xx..
..xx..
.xxxx.

 

 

---

 

풀이

 

구현 + 경로탐색 문제. 단지 주어진 조건을 잘 수행하며 구현했느냐로 문제풀이의 성패가 갈린다.

 

• throw : 막대를 던지는 행위를 구현한 함수. 홀수번째라면 오름차순, 짝수번째라면 내림차순으로 입력받은 행의 검사를 시작한다. 검사 도중 'x'표시를 만나면 이를 삭제 후 결과를 반환한다.
• bfs : 경로탐색 함수(BFS). 인접한 모든 'x'표시의 좌표를 탐색, 저장 후 그 좌표 리스트를 반환한다.
• cluster_move : 클러스트가 떠 있는 경우, 클러스터의 모든 좌표를 한 칸씩 아래로 내려가며 조건 일치 여부를 탐색한다(모든 좌표가 R, C내에 있는지, 좌표가 다른 'x'표시와 겹치지 않는지). 만약 조건을 벗어날 경우 그 직전 상태로 클러스터 표식을 변경한다.
• cluster_search : 맨 처음, 마지막 행에서 조건을 만족하는 경우에 대해 bfs를 실행한다. (즉 땅에 인접한 모든 클러스터 좌표를 얻을 수 있다). 그 다음 다른 모든 행을 순차적으로 검사하여 공중에 떠 있는 클러스터의 존재 유무를 알아내고, 만약 존재한다면 bfs를 호출하여 좌표 리스트를 반환받는다. 마지막으로 그 좌표 리스트를 cluster_move를 통해 조건에 맞도록 조정한다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

R, C = map(int, input().split())
cave_list = [list(input().strip()) for _ in range(R)]
N = int(input())
throw_list = list(map(int, input().split()))

def throw(r, order) :
  if order % 2 :
    _range = range(C-1, -1, -1)
  else :
    _range = range(C)
  for i in _range :
    if cave_list[r][i] == 'x' :
      cave_list[r][i] = '.'
      return True
  return False

def bfs(r, c, visited) :
  visited[r][c] = True
  visited_coord = [[r, c]]
  q = deque(visited_coord)
  while q :
    r, c = q.popleft()
    for k in range(4) :
      ar, ac = r + dr[k], c + dc[k]
      if -1 < ar < R and -1 < ac < C and not visited[ar][ac] and cave_list[ar][ac] == 'x' :
        visited[ar][ac] = True
        visited_coord.append([ar, ac])
        q.append((ar, ac))
  return visited_coord

def cluster_move(visited_coord) :
  for r, c in visited_coord :
    cave_list[r][c] = '.'
  flg = True
  i = 0
  while flg :
    i += 1
    for r, c in visited_coord :
      if r+i >= R or cave_list[r+i][c] == 'x' :
        flg = False
        break
        
  for r, c in visited_coord :
    cave_list[r+i-1][c] = 'x'

def cluster_search() :
  visited = [[False]*C for _ in range(R)]
  visited_coord = list()
  for i in range(C) :
    if not visited[-1][i] and cave_list[-1][i] == 'x' :
      bfs(R-1, i, visited)
  for i in range(R-1) :
    for j in range(C) :
      if not visited[i][j] and cave_list[i][j] == 'x' :
        visited_coord = bfs(i, j, visited)
        break
    if visited_coord :
      break
  if visited_coord :
    cluster_move(visited_coord)

for n in range(N) :
  is_movable = throw(R-throw_list[n], n)
  if is_movable :
    cluster_search()

for _cave in cave_list :
  print(''.join(_cave))

풀이 완료!