🥇[백준] 2638 치즈 (골드3) / 구현, 시간초과 해결, 문제 아이디어

문제요약

나의 코드 및 설명 01 (시간초과)

• 녹을 치즈가 더이상 없을 때까지 반복을 수행하면서 check_hole() 함수로 내부 공기의 좌표를 구하고, 치즈가 내부 공기 이외의 공기(외부 공기)와 2개 이상 맞닿아 있다면 녹을 예정인 치즈이므로, 리스트 r에 녹을 예정인 치즈의 좌표를 구하는 melt() 함수를 구현하였고, 그리드를 갱신해주도록 소스 코드를 작성했다.
• 매 반복마다 내부 공기 좌표를 구하는 check_hole() 함수를 통해, 매우 많은 좌표를 중복해서 여러번 탐색하기 때문에 시간 초과가 발생했다.  

#공기가 치즈 내부에 있는 공기인지 체크
def check_hole(arr):
    for y in range(n):
        for x in range(m):
            cnt = 0
            #공기(0)인 좌표
            if arr[y][x] == 0:
                for i in range(4): #상하좌우
                    for k in range(1,max(n,m)): #가로,세로의 끝까지 탐색
                        nx = x + k*dx[i]
                        ny = y + k*dy[i]
                        if 0<=nx<m and 0<=ny<n:
                            if arr[ny][nx] == 1: #치즈(1)를 만난다면,
                                cnt += 1 #cnt값을 카운트 해준다.
                                break
            if cnt == 4: #cnt가 4라면, 공기가 치즈로 둘러쌓인 것, 즉 내부공기이다.
                v.append((x,y)) #리스트 v에 내부공기 좌표 저장
    return

#녹을 치즈의 좌표를 구하는 함수
def melt(arr):
    for y in range(n):
        for x in range(m):
            check = 0
            if arr[y][x] == 1:
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<m and 0<=ny<n:
                        if (nx,ny) in v: #내부공기라면, 다음 방향 탐색
                            continue
                        elif arr[ny][nx] == 0:
                            check += 1 #외부 공기 카운트+1
                    if check == 2:
                        break 
            if check == 2: #밀접한 외부 공기가 2라면, 
                r.append((x,y)) #해당 치즈는 녹을 것이므로 리스트 r에 좌표 저장
    return


n, m = map(int, input().split()) #n:세로, m:가로

board = [list(map(int, input().split())) for _ in range(n)]

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


time = 0
while True:
    v = [] #내부에 있는 공기의 좌표 저장
    r = [] #녹아내릴 치즈의 좌표 저장
    check_hole(board)
    melt(board)
    if len(r) == 0:
        break
    while r:
        x, y = r.pop()
        board[y][x] = 0
    time += 1

print(time)

나의 코드 및 설명 02 (다른 사람의 힌트 참고)

• 외부의 공기와 2개 이상 맞닿아있다면 녹을 치즈라는 사실을 활용해, 외부 공기를 -1로 표기해주고 2개 이상의 외부 공기와 맞닿아 있는 치즈의 좌표를 구해서 문제를 해결하였다.
• 외부 공기 좌표 값을 -1로 바꾸는 bfs() 함수에서, 현재 좌표의 상하좌우의 좌표를 방문하게 되는데 방문할 좌표가 전체 그리드를 벗어났거나 치즈이거나 혹은 이미 방문한 좌표일 경우를 제외한 나머지 경우가 외부 공기인 경우이므로, if ~ : continue 를 활용해 조건의 나머지를 체크해주는 방식으로 코드를 작성하면 쉽다.

from collections import deque

#외부의 공기와 2개 이상 맞닿아있다면 녹을 치즈이다.

#외부 공기 좌표값을 -1로 바꿔주는 코드
def bfs(sx,sy):
    queue = deque()
    queue.append((sx,sy))
    v[sy][sx] = 1
    board[sy][sx] = -1

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            ##방문처리 안할 좌표 먼저 생각하면 쉽다.
            # 범위를 벗어나거나, 치즈(1)이거나, 이미 방문 했다면 continue한다. 
            if nx<0 or ny<0 or nx>=m or ny>=n:
                continue
            else:
                if board[ny][nx] == 1 or v[ny][nx] == 1:
                    continue
                else:   
                    v[ny][nx] = 1 #방문처리
                    board[ny][nx] = -1 #외부 공기 좌표값 -1로 표시
                    queue.append((nx,ny))
    return

#녹아내릴 치즈의 좌표 구하는 코드
def melt():
    for y in range(n):
        for x in range(m):
            if board[y][x] == 1:
                cnt = 0
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<m and 0<=ny<n:
                        if board[ny][nx] == -1: #외부 공기와 맞닿아있다면
                            cnt += 1 #cnt 값 +1
                if cnt >= 2: #cnt 값이 2 이상이라면, 즉 2개 이상의 외부 공기와 맞닿아 있다면
                    r.append((x,y)) #녹아내릴 치즈이므로 r에 해당 좌표 추가

n, m = map(int, input().split()) #n:세로, m:가로

board = [list(map(int, input().split())) for _ in range(n)]

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


r = []
time = 0
while True:
    r = []
    v = [[0]*m for _ in range(n)]
    bfs(0,0) #외부공기 -1로 표시
    melt() #녹아내릴 치즈의 좌표 구하기
    if len(r) == 0: #녹아내릴 치즈가 없다면 
        break #반복문 탈출
    while r:
        x,y = r.pop()
        board[y][x] = 0
    time += 1

print(time)

피드백

생각보다는 간단한 문제처럼 보였으나, 주어진 테스트케이스는 맞았지만 시간 초과가 발생했다. 혼자 힘으로 해결해보고 싶었으나 결국 힌트를 볼 수 밖에 없었고, 내부의 공기 좌표를 구하는 나의 생각과는 다르게 외부의 공기 좌표를 구하면 된다는 다른 사람의 아이디어를 보고 문제를 풀었다. 문제가 안풀리거나 비효율적으로 접근된다면 빠르게 다른 접근 방식을 생각해야만 하는데 아직 습관이 안되어있는 것 같다. 연습하다보면 언젠가 되겠지.. 문제를 많이 풀어봐야겠다.