BFS(백준 : 토마토-7576문제) 접근 방법

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

1. 생각해보기

- 검은색 : 처음에 생각한 부분
- 주황색 : 코딩을 하면서 추가된 부분 
- 파란색 : 문제 제출 및 방법을 찾아본 후 

1) 아이디어

M, N 입력받고, tomato 배열 생성, 

// 시작점 세팅

이중 for를 돌면서 tomato가 1이면 queue에 push하고 방문배열에도 0으로 세팅 <= 시작점은 무조건 1개라고 문제를 잘못 이해했었음. 하지만 바로 문제의 방향을 잘 찾음

// while (큐의 내용이 없어질때까지)

큐에 있는 값 하나씩 꺼내와서 상하좌우로 이동. 

// 배열 범위가 벗어난 경우

// 이미 방문한 경우는 제외

// tomato가 없는 경우(-1)인 경우, tomato가 익은 경우(1) 제외

 

// 방문배열에 기록

// queue에 추가

 

// bfs의 결과로 visited 배열을 순회하면서 모두 익을 수 없는 경우만, 최대값을 찾음 <= 여기에서 모두 시간 허비 (이중 for문을 사용하지 않으려고 while문에서 체크할 수 있는 방법은 고민함. 

 

// 고민을 시도한 부분

while문안에서 

let allNot = true; // 네가지 방향이 모두 불가능인지를 체크하는 변수 선언.

// if문에서 배열의 범위를 벗어나지 않고, 가고자 하는 방향에 모두 -1이 있다면 => 불가능으로 간주하고 -1을 리턴

 

AI 도움) 
while문이 도는 중간에는 절대 알 수 없습니다.
while문은 "도달할 수 있는 모든 칸을 다 방문하고 visited를 채우는" 역할만 합니다.
"불가능" 여부는 while문이 모두 끝난 후, visited 배열을 보면서 "혹시 tomato는 0인데 visited가 -1인(도달 못한) 칸이 있나?"라고 별도로 검사해야만 알 수 있습니다.

"막다른 길"에 있는 것과 "맵 전체가 불가능한" 것은 아무 상관이 없습니다.
전체가 불가능한지 알려면 BFS결과가 끝난 후에 알 수 있습니다. 

 

제가 생각했던 방법은 고립된 토마토가 있는지 였던 것 같습니다.

고립되었다 = 토마토를 익힐 수 없다 로 생각을 했었던 것 같습니다. 

 

고립되었다 = 토마토를 익힐 수 없다. 이부분은 맞지만 검증을 하는 부분(큐에서 가져온 데이터)은 이미 토마토가 익은 케이스라서 의미가 없었습니다. 만약, 토마토가 0인 기준으로 고립되었는지를 확인한다면, 가능할 수도 있을 것 같습니다.

 

하지만 이번 문제에서는 방문배열을 사용해서도 충분히 문제를 풀 수 있기 때문에 tomato배열과 방문 배열을 사용해서 문제를 풀었습니다. 

 

2) 시간복잡도

BFS O(V + E)

V는 1,000(M) * 1,000(N) = 1,000,000

E는 4 * V = 4,000,000

O (V + E) = 5,000,000 (1억미만의 연산 임으로 1초안에 가능)

O(MN + 4MN) = O(5MN) = O(MN) 의 시간복잡도를 가진다. 

 

보완하기) 

1. 시작점을 찾는 for문 O(MN)

2. BFS 시간 복잡도 O(MN)

3. 최종검사 O(MN)

=> 최종 O(MN) + O(MN) + O(MN) = O(3MN) = O(MN)이다. 

1,000,000 + 5,000,000 + 1,000,000 = 7,000,000 (1초안에 계산 가능)

 

 

 

3) 자료구조

큐

방문 배열

tomato, M,N

 

 

2. 직접풀어보기

https://github.com/moonlight-duck/study-algorithms/pull/22

[민주] BFS 문제풀이 2 by min-99 · Pull Request #22 · moonlight-duck/study-algorithms

 

결과)

결과