문제 바로가기
문제:
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다. 막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다. 미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다. 동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100) 다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다. 다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100) 마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다. 공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.
출력:
입력 형식과 같은 형식으로 미네랄 모양을 출력한다.
풀이:
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
r, c = map(int, sys.stdin.readline().split(" "))
graph = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(r)]
n = int(input())
height = list(map(int, sys.stdin.readline().split(" ")))
move = [(1, 0), (-1, 0), (0, -1), (0, 1)]
Q = deque()
# 하나 제거후 클러스터 상하좌우 미네랄 있는지 확인
def stick(i, flag):
# 짝수 왼쪽에서 쏠때
i = r - i
j = 0
# 왼쪽에서 날라옴
if flag == 1:
for k in range(c):
if graph[i][k] == "x":
graph[i][k] = "."
j = k
break
# 오른쪽에서 날라옴
else:
for k in range(c - 1, -1, -1):
if graph[i][k] == "x":
j = k
graph[i][k] = "."
break
# 깨진 거 기준 싱히좌우 미네랄 확인
for dx, dy in move:
nx = dx + i
ny = dy + j
if 0 <= nx < r and 0 <= ny < c:
if graph[nx][ny] == "x":
Q.append((nx, ny))
# 깨진 미네랄 상하좌우의 미네랄 리턴
# 없어진 미네랄 기준 생긴 클러스터 확인,
def lets_go_fall_visited(fall, visited):
# 내려갈 수 있는 범위 체크 해줌
# flag 바뀌면 바닥이라 못 내려감
down, flag = 1, False
while True:
for i, j in fall:
# down칸 내려가면 바닥일 경우
if i + down == r - 1:
flag = True
break
# 현재위치에서 donw+1 내려갔을때 다른 미네랄이 있으면 안됨.
if graph[i + down + 1][j] == 'x' and not visited[i + down + 1][j]:
flag = True
break
if flag:
break
down += 1
# 교체해주기
for i in range(r - 2, -1, -1):
for j in range(c):
if graph[i][j] == 'x' and visited[i][j]:
graph[i][j] = '.'
graph[i + down][j] = 'x'
def bfs(x, y):
q = deque()
visited = [[0] * c for _ in range(r)]
fall = []
q.append([x, y])
visited[x][y] = 1
while q:
x, y = q.popleft()
# 바닥이면 어차피 못 내려감
if x == r - 1:
return
# 각 열 마다 가장 아래에 있는 x,y좌표 가져옴
if graph[x + 1][y] == '.':
fall.append([x, y])
# 각 열마다 가장 아래 좌표까지 가기위해 탐색
for dx, dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] == 'x' and not visited[nx][ny]:
visited[nx][ny] = 1
q.append([nx, ny])
print('1')
# 그렇게 해서 나온 떨어진 클러스터의 가장 아래에 있는 좌표들과, 미네랄 좌표 체크리스트 들고감
# 없으면 밑에 조차 안감.
lets_go_fall_visited(fall, visited)
left = 1
for index in height:
# 미네랄 한개제거, 제거된 미네랄 기준 상하좌우 체크
stick(index, left)
while Q:
x, y = Q.popleft()
bfs(x, y)
left *= -1
break
for lst in graph:
print("".join(lst))
역대급으로 힘들었던 문제
1. 미네랄 제거
2. 미네랄 기준 상하좌우 미네랄확인
2-2 미네랄 있으면 떨어질 수 있는 후보
3. 후보들 다 bfs돌려봄 bfs돌렸는데 바닥이랑 연결되어있으면 떨어질리 없음
4. 바닥이랑 안 연결된 것중 가장 아래에 있는 좌표 falls에 들어감.
5. falls 를 1칸씩 내려보면서, 몇 칸 내려가는지 확인
댓글