백준 #2933 미네랄 (파이썬)

Yongjun Park·2022년 6월 11일
python백준
1

문제집: 단기간 성장

목록 보기
7/19

오늘의 한 마디
해설 거의 안 보고 풀었다. 엣지 케이스가 좀 있어서 시간 꽤 걸렸지만 뿌듯하다

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

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

예제 입력 2

8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1

예제 출력 2

........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.

예제 입력 3

7 6
......
......
xx....
.xx...
..xx..
...xx.
....x.
2
6 4

예제 출력 3

......
......
......
......
..xx..
xx.xx.
.x..x.

발상

막대기를 던져서 미네랄 하나 없애는 건 굉장히 간단하다. 

turn = CHANG_YOUNG
for h in H:
    # 1 -> R-1, 2 -> R-2, ..., R -> 0
    h = R-h
    mineral_y, mineral_x = -1, -1
    if turn == CHANG_YOUNG:
        mineral_y, mineral_x = throw_stick_from_left(h)
        turn = SANG_GEUN
    else:
        mineral_y, mineral_x = throw_stick_from_right(h)
        turn = CHANG_YOUNG

하지만 그렇게 없애놓고 다시 전체 미네랄에 대해서 어디까지가 클러스터인지 확인하기 위해,
매번 모든 미네랄에 대해서 BFS를 돌리고,
각각의 클러스터가 떠 있는지 확인하는 건 딱봐도 같은 일을 여러 번 하는 비효율적인 일이었다.

매번 같은 BFS를 돌리는건 비효율적이라는 생각은,
며칠 전 필자가 쓴 백준 #3197. 백조의 호수 글에서 학습했다.

이 글에서 BFS를 적게 할 힌트를 얻었다.
없어진 미네랄의 상하좌우만 검사하면 된다!

상하좌우 중 미네랄이 있다면, 그 미네랄 클러스터가 떠있는지 검사하면 된다.

Try #1 : 왜 틀렸을까?

(앞부분 생략)

def get_cluster_visited(start_y, start_x):
    visited = [[False]*C for _ in range(R)]
    q = deque([(start_y, start_x)])
    visited[start_y][start_x] = True
    while q:
        y, x = q.popleft()
        for dy, dx in DIRS:
            ny, nx = y+dy, x+dx
            if not (0 <= ny < R and 0 <= nx < C):
                continue
            if cave[ny][nx] == '.':
                continue
            if visited[ny][nx]:
                continue
            q.append((ny, nx))
            visited[ny][nx] = True
    return visited

def get_min_y_and_min_x_list(visited):
    x_list = []
    y = -1
    for y in range(R-1, -1, -1): # 바닥부터
        for x in range(C):
            if visited[y][x] == True:
                min_y = y
                min_x_list = [x for (x, val) in enumerate(visited[y]) if val == True]
                return min_y, min_x_list

def get_fall_height(min_y, min_x_list):
    min_diff = MAX_R + 1
    for x in min_x_list:
        for y in range(min_y + 1, R):
            if cave[y][x] == 'x':
                min_diff = min(min_diff, y - min_y - 1) # 처음 만난 미네랄이 5, min_y가 3이라면 1칸 내릴 수 있음
                break
            if y == R-1: # 바닥
                min_diff = min(min_diff, y - min_y) # 바닥이 5, min_y가 3이라면 2칸 내릴 수 있음
                # break # 어차피 마지막
    return min_diff

def fall(h, visited):
    # 아래서부터 내린다.
    for y in range(R-1, -1, -1):
        for x in range(C):
            if not visited[y][x]:
                continue
            cave[y][x] = '.'
            cave[y+h][x] = 'x'

turn = CHANG_YOUNG
for h in H:
    # 1 -> R-1, 2 -> R-2, ..., R -> 0
    h = R-h
    mineral_y, mineral_x = -1, -1
    if turn == CHANG_YOUNG:
        mineral_y, mineral_x = throw_stick_from_left(h)
        turn = SANG_GEUN
    else:
        mineral_y, mineral_x = throw_stick_from_right(h)
        turn = CHANG_YOUNG
    if (mineral_y, mineral_x) == (-1, -1): # 깨진 미네랄이 없을 때
        continue

    # 후보는, 없어진 미네랄의 상하좌우
    for dy, dx in DIRS:
        ny, nx = mineral_y + dy, mineral_x + dx
        if not (0 <= ny < R and 0 <= nx < C):
            continue
        if cave[ny][nx] == '.':
            continue
        # 주의. 클러스터가 떨어질 때, **그 클러스터 각 열의 맨 아래 부분 중 하나**가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다!
        visited = get_cluster_visited(ny, nx)      
        min_y, min_x_list = get_min_y_and_min_x_list(visited)

        if min_y == R-1:
            continue
            
        # 최저점이 바닥이 아닌 경우 == 현재 떠 있는 경우
        fall_height = get_fall_height(min_y, min_x_list)
        fall(fall_height, visited)
        break
        
print_cave()

틀렸습니다를 받았다.

예제 입출력은 정상적으로 나왔기 때문에 반례를 엄청나게 찾았고,
결국에는 문제를 잘못 이해했음을 깨달았다.

클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

이 말을, 클러스터에서 가장 낮은 부분이 바닥 또는 미네랄 위로 떨어진다 로 잘못 이해했다.

def get_min_y_and_min_x_list(visited):
    x_list = []
    y = -1
    for y in range(R-1, -1, -1): # 바닥부터
        for x in range(C):
            if visited[y][x] == True:
                min_y = y
                min_x_list = [x for (x, val) in enumerate(visited[y]) if val == True]
                return min_y, min_x_list

이렇게 찾는 게 아니라, 문제에서 나온 그대로 각 열의 맨 아래 부분의 y값을 저장해야 한다. 

def get_min_y_list(visited):
    min_y_list = [-1]*C
    for x in range(C):
        for y in range(R-1, -1, -1):
            if visited[y][x]:
                min_y_list[x] = y
                break
    return min_y_list

이렇게!

풀이

import sys
from collections import deque
CHANG_YOUNG, SANG_GEUN = 0, 1
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
MAX_R = 100

R, C = map(int, sys.stdin.readline().rstrip().split())
cave = []
for _ in range(R):
    cave.append(list(sys.stdin.readline().rstrip()))
    # 입력 받으면서 뭔가 할 수 있지 않을까? 
N = int(sys.stdin.readline().rstrip())
H = list(map(int, sys.stdin.readline().rstrip().split()))

# 매번 BFS 돌리는 건 에바고
# 매번 없앨 수 있는 미네랄은 한개
# 그 한개의 상하좌우에 미네랄이 있으면, 그 미네랄 섬이 떨어질 수도 있는 후보.
# 각 미네랄 섬에 대해서 BFS를 했을 때, 섬 중 최저 y 좌표를 구한다. 
# y 좌표가 0이면 break, 0이 아니면 그만큼 떨굼.
# https://chldkato.tistory.com/62

def throw_stick_from_left(h):
    for x in range(C):
        if cave[h][x] == 'x':
            cave[h][x] = '.'
            return h, x
    return -1, -1

def throw_stick_from_right(h):
    for x in range(C-1, -1, -1):
        if cave[h][x] == 'x':
            cave[h][x] = '.'
            return h, x
    return -1, -1

def print_cave():
    for row in cave:
        print(*row, sep='')

def get_cluster_visited(start_y, start_x):
    visited = [[False]*C for _ in range(R)]
    q = deque([(start_y, start_x)])
    visited[start_y][start_x] = True
    while q:
        y, x = q.popleft()
        for dy, dx in DIRS:
            ny, nx = y+dy, x+dx
            if not (0 <= ny < R and 0 <= nx < C):
                continue
            if cave[ny][nx] == '.':
                continue
            if visited[ny][nx]:
                continue
            q.append((ny, nx))
            visited[ny][nx] = True
    return visited

def get_min_y_list(visited):
    min_y_list = [-1]*C
    for x in range(C):
        for y in range(R-1, -1, -1):
            if visited[y][x]:
                min_y_list[x] = y
                break
    return min_y_list
            
def get_fall_height(min_y_list):
    min_diff = MAX_R + 1
    for x, min_y in enumerate(min_y_list):
        if min_y == -1: # 엣지 케이스
            continue
        for y in range(min_y + 1, R):
            if cave[y][x] == 'x':
                min_diff = min(min_diff, y - min_y - 1) # 처음 만난 미네랄이 5, min_y가 3이라면 1칸 내릴 수 있음
                break
            if y == R-1: # 바닥
                min_diff = min(min_diff, y - min_y) # 바닥이 5, min_y가 3이라면 2칸 내릴 수 있음
                # break # 어차피 마지막
    return min_diff

def fall(h, visited):
    # 아래서부터 내린다.
    for y in range(R-1, -1, -1):
        for x in range(C):
            if not visited[y][x]:
                continue
            cave[y][x] = '.'
            cave[y+h][x] = 'x'

turn = CHANG_YOUNG
for h in H:
    # 1 -> R-1, 2 -> R-2, ..., R -> 0
    h = R-h
    mineral_y, mineral_x = -1, -1
    if turn == CHANG_YOUNG:
        mineral_y, mineral_x = throw_stick_from_left(h)
        turn = SANG_GEUN
    else:
        mineral_y, mineral_x = throw_stick_from_right(h)
        turn = CHANG_YOUNG
    if (mineral_y, mineral_x) == (-1, -1): # 깨진 미네랄이 없을 때
        continue
    # 후보는, 없어진 미네랄의 상하좌우
    for dy, dx in DIRS:
        ny, nx = mineral_y + dy, mineral_x + dx
        if not (0 <= ny < R and 0 <= nx < C):
            continue
        if cave[ny][nx] == '.':
            continue
        # 주의. 클러스터가 떨어질 때, **그 클러스터 각 열의 맨 아래 부분 중 하나**가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다!
        visited = get_cluster_visited(ny, nx)
        
        # 오답.
        # 맨 아래 층에 있던 애들만 닿는 건 아니다!!!
        # **각 열**의 맨 아래 요소에 대해서 다 체크해야 함. 
        min_y_list = get_min_y_list(visited)
        
        if R-1 in min_y_list: # 바닥에 닿은 맨 아래 요소가 있다면
            continue
                    
        # 최저점이 바닥이 아닌 경우 == 현재 떠 있는 경우
        fall_height = get_fall_height(min_y_list)
        fall(fall_height, visited)

        # 주의. 두 개 이상의 클러스터가 동시에 떨어지는 경우는 없다. 
        break

print_cave()
profile
Yongjun Park
추상화되었던 기술을 밑단까지 이해했을 때의 쾌감을 잊지 못합니다
이전 포스트

백준 #10830 행렬 제곱 (파이썬)

다음 포스트

피보나치 수를 구하는 여러가지 방법 (파이썬)

0개의 댓글