글 읽기 - [2933] 미네랄 반례 모음

jeongbeen 3년 전 14

문제를 풀면서 만든 반례들 입니다.

5 5

xxxxx

x....

xxxxx

x....

10 1 2 3 4 5 1 2 3 4 5

>>output

.....
.....
.....
.xxxx
xxxx.

10 10
xxxxxxxxxx
....x.....
...xxx....
.....x....
....xx....
.....x....
xxxxxx....
..x.......
.xxxx.....
...xxxxxxx
10 9 8 7 6 5 4 3 2 1 1

>> output

..........
..........
..........
..........
..........
..........
xxxxxxxxxx
....xx....
xxxxxx....
.xxxxxxxx.

3 3
...
..x
x.x
2 1 1

>>output

...
...
..x

4 4
...x
..xx
xx.x
x..x
2 1 1

>>output

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

4 4
...x
..xx
.xxx
xxxx
10 1 2 3 4 1 2 3 4 3 4

>>output

....
....
.xxx
..xx

fail456 3년 전 0

첫번째 예제 케이스의 경우

첫번째 동작 이후

.....

xxxxx

x....

xxxxx

x....

이런 모양이 되고

두번째 동작을 하게 되면

.....

xxxxx

x....

.xxxx

x....

이런 모양이 되어서 클러스터 2개가 떨어져야 하는 상황이 나오는데 적절하지 않은 예시가 아닐까요?

jeongbeen 3년 전 1

본문에 '첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.' 라고 되어있으니,

첫번째 동작 이후

.....

xxxxx

x....

xxxxx

x....

이런 모양이 되고

두번째 동작을 하게 되면

.....

xxxxx

x....

xxxx.

x....

이렇게 될 것 같습니다.

fail456 3년 전 1

아이고 좀 더 생각하고 댓글을 남겼어야 했는데 생각이 짧았네요.

좋은 반례들 감사합니다!

저도 정빈님 반례 써가면서 문제 해결했어요!

좋은 하루 되세요!

rjwltps57 3년 전 1

감사합니다...

제코드는 다른 모든 예시 다 맞는데 11퍼센트에서 틀려서 미치겠네요..

edlsw 3년 전 0

rjwltps57
와 저랑 똑같은 고민 중이신가보네요...

저도 게시판 다 뒤지면서 해보고 있는데 왜 틀리는지를 모르겠어서 미치겠습니다ㅠㅠ

scw1544 3년 전 0

@rjwltps57

문제 해결하신지 좀 되셨겠지만.. 혹시 어떻게 해결하셨나요?

저도 11퍼센트에서 계속 틀려서 하루종일 고민하고 있습니다... 이 문제만 몇 시간째인지ㅠㅠㅠㅠ 답답하네요..

rjwltps57 3년 전 4

백준 댓글 시스템이 있는지 모르고 답변을 늦게 드립니다ㅠㅠ

1. 만약 벽을 부순다면, 3방향을 조사해야 합니다. (위, 옆, 심지어 아래까지) 저는 처음에 아마 아래는 조사하지 않았던 기억이 어렴풋 나네요,,

2. 떨어지는 단계에서, 맨 밑 바닥과의 거리간의 차이만큼 떨어질 수 있습니다. 하지만 바닥과의 차이 뿐 아니라, 다른 미네랄(떨어지지 않는 미네랄과의 차이도 신경 쓰셔야 합니다)

이 두가지 모두 고려해보셨나요?

scw1544 3년 전 0

@rjwltps57

음.. 우선 답변 정말 감사합니다!!

말씀해주신 2번 경우는 고려했습니다.

근데 1번 경우에서 옆과 아래는 고려했는데.. 위를 조사하는 건 어떤 경우인지 잘 모르겠습니다..ㅠㅠ

혹시 몰라 코드! 놓고 가겠습니다..

조언해주실 분 있으시면 감사히 받겠습니다!

import sys
input = sys.stdin.readline
from collections import deque

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

# 탐색 시작열과 마지막열 인자로 넣으면 떨어질 수 있는 가장 작은 차이를 리턴
def down(left, right):
    min_gap = R
    for c in range(left, right+1):
        flag = False
        cnt = 0
        for r in range(R):
            if visited[r][c] == 2:
                flag = True
                cnt = 0
            elif flag and visited[r][c] == 0 and cave[r][c] == '.':
                cnt += 1
            elif visited[r][c] == 1:
                break
        min_gap = min(min_gap, cnt)
    return min_gap

def bfs(sr, sc, num):
    global visited, cave
    visited[sr][sc] = num
    Q = deque([(sr, sc)])
    minerals = [(sr, sc)]
    while Q:
        r, c = Q.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < R and 0 <= nc < C):
                continue
            if cave[nr][nc] == 'x' and not visited[nr][nc]:
                visited[nr][nc] = num
                Q.append((nr, nc))
                if num == 2:
                    minerals.append((nr, nc))
    if num == 2:    # 공중에 떠있을 때
        minerals.sort(key=lambda x: x[1])
        left, right = minerals[0][1], minerals[-1][1]
        gap = down(left, right)     # 떨어질 수 있는 최소 차이
        mlen = len(minerals)        # 미네랄 갯수
        new_minerals = []           # 미네랄의 새 위치 담으면서 빈 공간으로 만들어주기
        for i in range(mlen):
            mr, mc = minerals[i]
            cave[mr][mc] = '.'
            visited[mr][mc] = 0
            new_minerals.append((mr+gap, mc))

        for i in range(mlen):
            nr, nc = new_minerals[i]
            cave[nr][nc] = 'x'           # 미네랄 새 위치에 뿌리기
            visited[nr][nc] = 1

# 땅에 붙어 있는 클러스터는 1 표시, 공중에 떠 있는 클러스터는 2 표시
def check():
    global visited
    for c in range(C):
        if cave[R-1][c] == 'x' and not visited[R-1][c]:
            bfs(R-1, c, 1)     # 땅에 붙어 있는 클러스터 1로 방문처리

    for r in range(R-1):
        for c in range(C):
            if cave[r][c] == 'x' and not visited[r][c]:
                bfs(r, c, 2)    # 공중에 떠있는 클러스터 2로 방문처리

# main
R, C = map(int, input().split())
cave = [list(input().strip()) for _ in range(R)]
N = int(input())
info = list(map(int, input().split()))

heights = [R - info[i] for i in range(N)]    # 높이 정보 변환
for i in range(N):
    tag = 0
    if not i % 2:   # 짝수 인덱스일 때 왼쪽에서 날아옴
        for j in range(C):
            if cave[heights[i]][j] == 'x':
                cave[heights[i]][j] = '.'
                tag = 1
                break
    else:           # 홀수 인덱스일 때 오른쪽에서 날아옴
        for j in range(C-1, -1, -1):
            if cave[heights[i]][j] == 'x':
                cave[heights[i]][j] = '.'
                tag = 1
                break
    if tag:         # 미네랄 깼으면
        visited = [[0] * C for _ in range(R)]
        check()     # 각 클러스터가 땅에 붙어있는지
for row in cave:
        print(''.join(row))

unsung0317 3년 전 2

다른 분들 댓글 보고 겨우 맞췄습니다.

아래에 남겨진 것은 확인 할 필요가 없다고 생각했는데, 계속 11퍼에서 틀렸습니다. 나오더라구요.

반례 하나 남기고 갑니다. 아래 확인 안하면 결과가 안나오게 만들었습니다.

3 3

xxx

x.x

..x

예상 결과

.xx

..x

x.x

저의 실수

.xx

x.x

..x

결과적으로 위, 옆, 아래 다 확인해서 1번이라도 발생하면 종료하고 아니면 3면을 다확인해야 하는 문제네요.

댓글들 모두 감사합니다. (다른 분들 정말 내공이 느껴지네요. ㅠㅠ)

unsung0317 3년 전 4

추가적으로 부서진 위치에서 위, 옆, 아래 다 확인해야 경우 추가합니다.

4 4

xxxx

xx.x

x..x

...x

예상 결과

xxxx

.x.x

...x

x..x

last_remote 2년 전 1

아래도 확인해야 한다는 점을 놓쳐서 한참 걸렸네요.

댓글분들 감사합니다.

kimsd1983 2년 전 0

이거 보면서 버그 두 개 찾았습니다 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[2933] 미네랄 반례 모음

jeongbeen 3년 전 14

fail456 3년 전 0

jeongbeen 3년 전 1

fail456 3년 전 1

rjwltps57 3년 전 1

edlsw 3년 전 0

rjwltps57
와 저랑 똑같은 고민 중이신가보네요...

저도 게시판 다 뒤지면서 해보고 있는데 왜 틀리는지를 모르겠어서 미치겠습니다ㅠㅠ

scw1544 3년 전 0

rjwltps57 3년 전 4

scw1544 3년 전 0

unsung0317 3년 전 2

unsung0317 3년 전 4

last_remote 2년 전 1

kimsd1983 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

[2933] 미네랄 반례 모음

jeongbeen 3년 전 14

fail456 3년 전 0

jeongbeen 3년 전 1

fail456 3년 전 1

rjwltps57 3년 전 1

edlsw 3년 전 0

rjwltps57와 저랑 똑같은 고민 중이신가보네요...

저도 게시판 다 뒤지면서 해보고 있는데 왜 틀리는지를 모르겠어서 미치겠습니다ㅠㅠ

scw1544 3년 전 0

rjwltps57 3년 전 4

scw1544 3년 전 0

unsung0317 3년 전 2

unsung0317 3년 전 4

last_remote 2년 전 1

kimsd1983 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

rjwltps57
와 저랑 똑같은 고민 중이신가보네요...