문제#
- 링크로 대체
풀이 및 주저리..
저번주에 2문제 풀었던 것을 반성하며 백준 단계별 풀기 한 문제를 더 풀어보았다. 간단한 BFS에서 조금 더 응용된 시작 위치가 여러곳일 수 있고 조금더 생각해야할게 많은 문제였다. 어떻게 풀지 고민을 하다가 익어있는 토마토의 위치를 큐에 넣어 기억해 두고 후에 각각의 위치에서 BFS 를 시작하면서 마지막에 토마토 배열을 순회하면서 가장 큰수를 찾는 방식으로 풀어보았다. 예외로는 0이 존재하면 바로 -1을 반환해줄 수 있게 함수를 통해서 정답을 구해보았고 재밌게 풀어본 문제였다.
코드
package baekjoon.algorithm.dfsbfs;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Problem7576 {
static final int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
sc.nextLine();
int[][] tomatoMap = new int[m][n];
Queue<Integer> que = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
tomatoMap[i][j] = sc.nextInt();
if (tomatoMap[i][j] == 1) {
que.add(i);
que.add(j);
}
}
sc.nextLine();
}
while (!que.isEmpty()) {
int x = que.poll();
int y = que.poll();
for (int i = 0; i < 4; i++) {
int mX = x + dx[i];
int mY = y + dy[i];
if (mX >= 0 && mX < m && mY >= 0 && mY < n && tomatoMap[mX][mY] == 0) {
tomatoMap[mX][mY] = tomatoMap[x][y] + 1;
que.add(mX);
que.add(mY);
}
}
}
System.out.println(checkMap(tomatoMap));
}
public static int checkMap(int[][] tomatoMap) {
int answer = 0;
for (int i = 0; i < tomatoMap.length; i++) {
for (int j = 0; j < tomatoMap[i].length; j++) {
if(tomatoMap[i][j] == 0) return -1;
if(answer < tomatoMap[i][j]) answer = tomatoMap[i][j];
}
}
return answer - 1;
}
}기억에 남길 것!
- 무