Baekjoon 7576번 토마토

문제

https://www.acmicpc.net/problem/7576

걸린 시간

01 : 38 : 25

풀이

PyPy3

import sys
input = sys.stdin.readline

from collections import deque

class Node():
    def __init__(self, v):
        self.vertex = v
        self.link = None

class listGraph():
    def __init__(self):
        self.n = 0 # vertex count
        self.adj_list = []

    # adj_list 의 인덱스를 정점의 번호로 설정
    def insert_vertex(self):
        self.adj_list.append(None)
        self.n += 1

    # v값을 u의 인접 리스트에 삽입
    def insert_edge(self, u, v): 
        new = Node(v)
        if u > self.n-1 or v > self.n-1:
            print("out of area")    
        else:
            new = Node(v)
            new.vertex = v
            new.link = self.adj_list[u]
            self.adj_list[u] = new

def check_loc(g, u_r, u_c, v_r, v_c, warehouse):
    if v_r < 0 or v_c < 0 or v_r > len(warehouse)-1 or v_c > len(warehouse[0])-1:
        return    

    u = warehouse[u_r][u_c]
    v = warehouse[v_r][v_c]

    if v != -1:
        g.insert_edge(u, v)

def bfs():
    q = deque()
    visited = [False for _ in range(0, g.n)]

    # 익지 않은 토마토가 없는 상황이면 0
    if len(ripe_tomato) == 0:
        return 0

    # 익은 토마토를 기준으로 bfs 탐색
    for v in ripe_tomato:
        visited[v] = True
        q.append([v, 0])

    while q:
        v, l = q.popleft()
        l += 1    
        w = g.adj_list[v]
        while w != None:
            if not visited[w.vertex]:
                visited[w.vertex] = True
                q.append([w.vertex, l])
            w = w.link

    # 방문되지 않은 정점이 존재하면
    visited = set(visited)

    if len(visited) > 1:
        return -1
    else:
        return l-1

if __name__ == "__main__":
    M, N = map(int, input().strip().split())

    warehouse = []

    for _ in range(0, N):
        warehouse.append(list(map(int, input().strip().split())))

    g = listGraph()
    v = 0 # vertex
    ripe_tomato = []

    for r in range(0, N):
        for c in range(0, M):
            tomato = warehouse[r][c]

            # 토마토가 있으면
            if tomato != -1:
                g.insert_vertex()
                warehouse[r][c] = v

                # 익은 토마토이면 
                if tomato == 1:
                    ripe_tomato.append(v)

                v += 1

    for r in range(0, N):
        for c in range(0, M):
            if warehouse[r][c] != -1:
                check_loc(g, r, c, r, c+1, warehouse) # up 
                check_loc(g, r, c, r, c-1, warehouse) # down 
                check_loc(g, r, c, r-1, c, warehouse) # left
                check_loc(g, r, c, r+1, c, warehouse) # right

    print(bfs())

Python3 으로는 시간초과가 나서 보다 빠른 PyPy3 로 제출하였을때 통과한 소스코드. 상당히 길어 보이지만 코드의 1/3은 리스트로 구현한 그래프 자료구조에 해당되는 부분이다.

코드에 대해 간단히 설명하자면 토마토 창고 역할을 하는 2차원 리스트에 토마토가 있을 경우, 값을 0부터 시작하는 정점의 번호로 바꾸어 주었다.

그리고 상하좌우 인접한 토마토들을 모두 연결시킨 후 익은 토마토들을 큐에 집어놓고 BFS 를 시작했다.

그래프를 완성시킨 후 탐색하여 정답을 찾아내기 때문에 정답은 맞았지만 비효율적이다.

다른 풀이

Python3

from collections import deque

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

def bfs():
    result = 0
    while q:
        result += 1
        for _ in range(len(q)):
            x, y = q.popleft()
            for i in range(0, 4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < M:
                    if warehouse[nx][ny] == 0:
                        warehouse[nx][ny] = 1
                        q.append([nx, ny])
    return result

if __name__ == "__main__":
    M, N = map(int, input().split())
    q = deque()
    warehouse = []

    for r in range(0, N):
        row = list(map(int, input().split()))
        for c in range(0, M):
            if row[c] == 1:
                q.append([r, c])
        warehouse.append(row)

    result = bfs()-1

    for r in range(0, N):
        for c in range(0, M):
            if warehouse[r][c] == 0:
                print(-1)
                exit()

    print(result)

Python3 으로 통과한 분의 소스코드를 보니 배워갈 몇가지 눈에 띄는 부분이 있어 참고하여 다시 구현해보았다.

1. 토마토 창고의 정보를 입력받으며 익은 토마토의 좌표를 큐에 저장
2. dx, dy 두개의 리스트를 사용해 간단히 상하좌우 위치를 탐색