글 읽기 - 2%에서 틀렸네요....ㅠㅠ

eui20n 1년 전 0

높이가 가장 낮은 곳 ~ 높이가 가장 높은 곳 ==> 각각의 높이에서 고일 수 있는지, 있으면 몇개가 고이는지 체크하는 식으로 했는데 2%에서 틀렸다고 뜨네요.....

수영장을 꼭 만들고 싶은데, 혹시 반례 케이스가 있을까요??

from collections import deque

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


def visited_init():
    """ 방문 처리 리스트를 만들어 주는 함수 """
    visited = [[False] * C for _ in range(R)]
    return visited


def find_min_max():
    """ 최소값과 최대값을 찾아주는 함수 """
    max_num = 0
    min_num = float('inf')

    for x in range(R):
        for y in range(C):
            if graph[x][y] > max_num:
                max_num = graph[x][y]

            if graph[x][y] < min_num:
                min_num = graph[x][y]

    return [min_num, max_num]


def make_pool(x, y, layer, visited):
    """ 수영장을 만들어 주는 함수 """
    # 잠길 곳이 없어서 0을 반환해줌
    if graph[x][y] > layer:
        visited[x][y] = True
        return 0

    if x == 0 or y == 0 or x == R - 1 or y == C - 1:
        check_connect(x, y, visited, layer)
        return 0

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    visited[x][y] = True

    q = deque()
    q.append([x, y])
    result = 1

    while q:
        x, y = q.popleft()

        for z in range(4):
            nx = x + dx[z]
            ny = y + dy[z]
            if make_pool_con(nx, ny, visited, layer):
                if nx == 0 or nx == R - 1 or ny == 0 or ny == C - 1:
                    check_connect(nx, ny, visited, layer)
                    return 0

                q.append([nx, ny])
                visited[nx][ny] = True
                result += 1

    return result


def make_pool_con(x, y, visited, layer):
    """ make_pool의 조건 함수 """
    if 0 > x or x >= R:
        return False
    if 0 > y or y >= C:
        return False
    if visited[x][y]:
        return False
    if graph[x][y] > layer:
        return False
    return True


def check_connect(x, y, visited, layer):
    """ 가장 자리와 만나는 것이 뭔지 알려주는 함수 """

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    visited[x][y] = True

    q = deque()
    q.append([x, y])

    while q:
        x, y = q.popleft()

        for z in range(4):
            nx = x + dx[z]
            ny = y + dy[z]
            if make_pool_con(nx, ny, visited, layer):
                visited[nx][ny] = True
                q.append([nx, ny])


def main():
    """ 함수를 실행 시키는 함수 """
    cnt = 0

    min_num, max_num = find_min_max()

    for layer in range(min_num, max_num + 1):
        visited = visited_init()

        for x in range(R):
            for y in range(C):
                if not visited[x][y]:
                    cnt += make_pool(x, y, layer, visited)

    return cnt


print(main())

eui20n 1년 전 1

9 13

1111111111111

1555555555551

1511111111151

1511199911151

1511192911151

1511199911151

1511111111151

1555555515551

1511111111151

이게 반례였네요.....

한번 간 곳의 visited을 True로 해서 다시 check_connect로 들어갈때 그 곳을 못가서 생기는 반례입니다 -> 이미 들어가서 주위가 True되서 못가는 경우

(위 예제에서는 (6,10) 에서 해당 예외가 생깁니다.)

저 같은 실수하지 마세요~

codebabo 1년 전 0

저도 사소한 실수를 위의 반례로 찾았네요.

예제 감사합니다.

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

문제

문제

출처

ICPC

2%에서 틀렸네요....ㅠㅠ

eui20n 1년 전 0

eui20n 1년 전 1

codebabo 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말