글 읽기 - 2638번 치즈

alsgh5821 3년 전 0

출력 초과가 나오는데 이유를 모르겠습니다 ㅠㅠㅠ

문제를 푼 방법은

1. 치즈를 기준으로 상,하,좌,우에서 각각 DFS를 수행하여 모눈종이를 벗어난 경우가 2곳 이상일시 외부에 노출됐다고 판단

2. 치즈를 기준으로 상,하,좌,우에서 DFS를 시작하기전 상,하,좌,우의 위치가 치즈로 막혀있다면 DFS를 하지 않는다

3. 모든 치즈에 대해서 상,하,좌,우 에서 DFS를 수행

4. 모든 치즈에 대해서 상,하,좌,우 DFS를 통해 외부와 2곳이상 접촉한 치즈를 발견한 후, 얘네들은 삭제

5. 1번으로 돌아가 반복

n, m = list(map(int, input().split()))

data = []   # 초기 맵 리스트
for _ in range(n):
    data.append(list(map(int, input().split())))

temp = [[0] * m for _ in range(n)]  # 벽을 설치한 뒤의 맵 리스트
for i in range(n):
    for j in range(m):
        temp[i][j] = data[i][j]

for i in range(n):
    print(data[i])

# 4가지 이동 방향에 대한 리스트
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

time = 0     # 치즈가 모두 녹아 없어지는데 걸리는 시간

count = 0
# 깊이 우선 탐색(DFS)을 통해 치즈가 외부와 맞닿아 있는 면이 몇개인지 찾음
def cheeze(x, y):
    global count
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 벽을 넘어서는 경우
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            count =1
            continue
        if data[nx][ny] == 1:
            continue
        if data[nx][ny] == 0:
            data[nx][ny] = 2
            cheeze(nx, ny)
            data[nx][ny] = 0

# 치즈가 남아있는지 확인
def check():
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 1:
                return True
    return False


# 모눈종이 위의 모든 치즈에 대해서, 각각 상,하,좌,우가 외부와 접촉하고 있는지 검사
while True:
    time += 1
    result = 0
    for i in range(n):
        for j in range(m):
            if i != 0 and j != 0 and i != n-1 and j != m-1 and data[i][j] == 1:
                # 현재 치즈의 위쪽 공간이 비어있을 경우
                if data[i-1][j] == 0:
                    cheeze(i-1, j)
                    result += count
                    count = 0

                # 현재 치즈의 아래쪽 공간이 비어있을 경우
                if data[i + 1][j] == 0:
                    cheeze(i+1, j)
                    result += count
                    count = 0

                # 현재 치즈의 왼쪽 공간이 비어있을 경우
                if data[i][j-1] == 0:
                    cheeze(i, j-1)
                    result += count
                    count = 0

                # 현재 치즈의 오른쪽 공간이 비어있을 경우
                if data[i][j+1] == 0:
                    cheeze(i, j+1)
                    result += count
                    count = 0

                if result >= 2:
                    temp[i][j] = 0
                result = 0

    if check() == False:
        break
    else:
        for i in range(n):
            for j in range(m):
                data[i][j] = temp[i][j]


print(time)

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

문제

문제

출처

ICPC

2638번 치즈

alsgh5821 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말