[Python Gold V 7576]

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

7576번: 토마토

2차원 크기가 주어지고.

그 크기만큼 정보를 입력받습니다.

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

1은 익은 토마토, 0은 일반 토마토, -1 비어있는 칸 입니다.

한 턴마다 익은 토마토 상하좌우에 있는 일반토마토가 익습니다. 이때 모든 토마토가 익는 턴수를 구하는 문제입니다.

 

1. 재귀함수

2. for문

두 가지 방법 모두 비슷하지만.

처음 제가 생각대로 짠 코드는 2. for문을 이용한 방식입니다.

익은 토마토 위치를 체크하고 for문을 사용해서 상하좌우를 익게 만들고 그 횟수를 세는 방식입니다.



첫 번째 방법이 시간 초과 때문에 통과를 못 해서 재귀함수로 한 번 더 만들어보았습니다.

구조상 for 문이랑 별다른 건 없습니다. 이전과 변환 후 리스트를 비교하고 달라진 게 없으면, 빈칸에 막혀서 변하지 못한 토마토가 있는지 체크 한후 재귀함수를 탈출합니다

이 코드 또한 시간 초과였습니다.

그래서 어쩔 수 없이 인터넷을 찾아본 결과. 이문제는 Deque를 사용해서 풀면 되는 문제였습니다.

제가 한 방식과 유사하지만 Deque를 사용함으로써 시간복잡도를 효과적으로 단축할 수 있었습니다.

 

실버 문제들은 제가 생각하는 대로 코딩을 해서 풀어도 시간초과가 나오는 경우는 거의 없었습니다. 하지만 골드 문제부터는 문제를 구현하는 거 뿐만 아니라 시간복잡도도 고려해야 되는 점이 조금 더 어려운 것 같습니다.