[백준] 18500번 : 미네랄 2

18500번: 미네랄 2

18500번: 미네랄 2

📄 문제개요

창영이와 상근이는 양쪽에서 화살을 날려 미네랄를 부순다. 미네랄을 부수면 땅과 연결되지 않는 클러스터는 모양을 유지한 상태로 땅이나, 다른 미네랄 혹은 클러스터에 떨어진다.

주어진 창을 던지는 횟수와 높이가 주어졌을때, 최후의 미네랄의 모양을 출력하라.

🤔 문제분석

R, C, N 이 100 이하 이기때문에 정확한 문제 분석과 알고리즘 작성이 문제의 Key Point 라고 생각한다.

1. 주어진 창의 횟수가 높이가 주어졌을때 미네랄을 부수는 알고리즘을 작성한다.
2. 땅과 연결되지 않는 클러스터 그룹을 모두 구하는 알고리즘을 작성한다.
3. 클러스터가 떨어지는 알고리즘을 작성한다.

📝 의사코드

1. 주어진 화살 높이를 순회한다.
   1. 화살 공격을 받은 미네랄을 삭제한다 ( attack 함수 )
   2. 땅과 연결되지 않는 클러스터 그룹을 찾는다. ( find_air_mineral 함수 )
   3. 땅과 연결되지 않는 클러스터 그룹을 떨어 뜨린다. ( move 함수 )
2. 주어진 화살 높이를 순회가 끝나면 미네랄 상태를 출력한다.

💻 코드

import sys
from collections import deque

input = sys.stdin.readline

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

toggle = False # false가 왼쪽, true 가 오른쪽

def attack(h, dir):
    start = 0
    if dir:
        start = C-1
        
    while C > start >=0 and graph[h][start] == '.':
        if dir:
            start -= 1
        else:
            start += 1
            
    if C > start >=0 and graph[h][start] == 'x':
        graph[h][start] = '.'

def find_air_mineral():
    groups = []
    visited = [[False for _ in range(C)] for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if graph[i][j] == 'x' and not visited[i][j]:
                visited[i][j] = True
                queue = deque()
                temp = []
                is_land = False
                queue.append((i, j))
                temp.append((i, j))
                while queue:
                    y, x = queue.popleft()
                    if y == R-1:
                        is_land = True
                    for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                        ny, nx = y + dy, x + dx
                        if R > ny >= 0 and C > nx >= 0 and not visited[ny][nx] and graph[ny][nx] == 'x':
                            visited[ny][nx] = True
                            temp.append((ny, nx))
                            queue.append((ny, nx))
                
                if not is_land:
                    groups.append(temp)
                
    return groups
    
def move(group):
    queue = deque()
    for q in group:
        queue.append((q[0], q[1], 0))
        graph[q[0]][q[1]] = '.'
        
    while queue:
        y, x, cost = queue.popleft()
        
        if y == R-1 or graph[y+1][x] == 'x':
            for n_y, n_x in group:
                graph[n_y + cost][n_x] = 'x'
            break
                
        queue.append((y+1, x, cost + 1))
            
for i in range(N):
    attack(R-arrow[i], toggle)
    toggle = not toggle
        
    groups = find_air_mineral()
    for group in groups:
        move(group)

for p in graph:
    print(''.join(p))

🎯 피드백 및 개선사항

문제의 포인트는 너비우선탐색의 응용이라고 생각한다. 너비우선탐색으로 2번과 3번 알고리즘을 작성하였다.

❓다른사람은 어떻게 풀었을까?

다른 풀이도 너비우선탐색으로 문제를 해결하였습니다.