• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

문제 예외처리에 관한 질문

23.12.22 00:45 작성 조회수 107

0

안녕하세요 선생님. 강의 잘 듣고 있습니다.

선생님의 풀이를 보니, 처음부터 모든 토마토가 익어있는 경우와 익은 토마토가 하나도 없는 경우는 안넣으신거같은데, 따로 이유가 있을까요?

 

또한, 아래는 제 풀이코드인데 dis 배열을 만들어서 선생님 풀이처럼 하는 것보다 복잡도가 높을까요?

 

import sys
from collections import deque
sys.stdin = open('in5.txt','r')

def total_search(arr,m,n):
    li = [0,0,0] # 토마토상태별로 갯수저장하는 갯수
    for i in range(n):
        for j in range(m):
            # 토마토가 없는 경우
            if arr[i][j] == -1:
                li[0] += 1
            # 토마토가 안익은 경우
            elif arr[i][j] == 0:
                li[1] += 1
            # 토마토가 익은 경우
            else:
                li[2] += 1
                dq.append((i,j,0))
    return li


if __name__ == "__main__":
    m, n = map(int,input().split()) # m = 가로, n = 세로
    arr = [list(map(int,input().split())) for _ in range(n)]  # 맵 정보
    dq = deque() # 익은 토마토 인덱스 저장 큐
    dy = [-1,0,1,0]
    dx = [0,1,0,-1]

    # 토마토 상태를 파악하는 함수
    li = total_search(arr,m,n)

    # 익은 토마토가 하나도 없는 경우
    if li[2] == 0:
        print(-1)
        sys.exit()
    # 처음부터 모든 토마토가 익어있을 경우
    elif li[2] == m*n :
        print(0)
        sys.exit()

    # 익는 과정 연산
    while dq:
        tmp = dq.popleft()
        y,x,d = tmp[0],tmp[1],tmp[2] # y,x 인덱스, d는 날짜

        # 상하좌우 연산
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            # 안익은 토마토일 경우
            if 0<=ny<=n-1 and 0<=nx<=m-1 and arr[ny][nx] == 0:
                # 익은 토마토로 바꾸고
                # 날짜 하나 올려서 큐에 추가
                arr[ny][nx] = 1
                dq.append((ny,nx,d+1))

    # 토마토 상태 갱신
    li = total_search(arr,m,n)

    # 토마토가 다 익지 못한 경우
    if li[1] != 0:
        print(-1)
    else:
        print(d)

답변 1

답변을 작성해보세요.

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2023.12.24

안녕하세요, 인프런 AI 인턴입니다.

대식님의 질문에 답변드리겠습니다.

선생님께서 강의에서 모든 토마토가 처음부터 익어있는 경우나 익은 토마토가 하나도 없는 경우를 강의 내용에서 배제하신 정확한 이유는 제가 확인할 수 없으나, 일반적으로 코딩 테스트 문제 풀이에서 모든 경우를 따져가며 예외 처리를 해야 할 때가 있습니다. 문제의 조건이나 제약사항에 따라 해당 상황들을 묵시적으로 배제하거나 간단히 처리할 수 있기 때문에 강의에서 특별히 다루지 않았을 수 있습니다.

단, 실제 코딩 테스트 시나 개발 중에는 이러한 예외 케이스를 고려하는 것이 매우 중요합니다.

대식님의 풀이 코드를 살펴보면 dis 배열 없이 주어진 문제를 해결하는 로직을 구현하셨습니다. 대식님의 접근 방식은 큐를 사용하여 익은 토마토의 위치를 관리하면서 BFS(너비 우선 탐색)를 수행하는 전통적인 방식으로 보입니다. 복잡도에 관한 질문에 대해선, 작성하신 코드에서도 BFS 알고리즘의 시간 복잡도는 보통 O(|V|+|E|)로 표현되며, 여기서 |V|는 정점의 수, |E|는 간선의 수를 의미합니다.

토마토판(m*n 크기)에서 따져보면 각 토마토 칸을 정점으로 보고, 인접한 칸으로 이동할 수 있는 경우를 간선으로 본다면 디테일한 복잡도 분석이 필요하지만, 일반적인 경우 2차원 배열에서의 BFS 진행 복잡도는 O(m*n)으로 생각해볼 수 있습니다.

다시 말해, 별도의 dis 배열을 만들어서 해결하는 것과 단순히 방문 여부만 체크하는 것은 공간 복잡도에 있어서 차이는 있을 수 있으나, 시간 복잡도는 크게 차이 나지 않을 것으로 예상됩니다. 물론, 구현의 세부적인 차이에 따라 다소 이러한 복잡도는 달라질 수 있습니다만 주어진 조건에서 볼 때 대식님의 풀이 방식이 특별히 비효율적으로 보이지는 않습니다.

코딩을 하시면서 다양한 방법으로 문제를 해결하는 경험이 중요하므로 대식님의 접근 방식을 통해 다른 방식의 해결책도 고민해보시는 것이 좋습니다.

계속해서 열심히 학습하셔서 좋은 결과 얻으시길 바랍니다.

화이팅입니다!