백준 7576번 : 토마토
문제 풀이
- 접근법 :BFS
모든 원소를 순회하면서, 익은 토마토를 시작점으로 BFS를 수행하여 최단 날짜를 구해나간다.
java 구현 코드
package ch08_BFS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class p7576_solved {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int M = Integer.valueOf(st.nextToken());
int N = Integer.valueOf(st.nextToken());
Queue<Position> queue = new LinkedList<>();
int[][] tomatoes = new int[N][M];
boolean[][] visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
tomatoes[i][j] = Integer.valueOf(st.nextToken());
if (tomatoes[i][j] == 1) {
queue.add(new Position(i, j));
visited[i][j] = true;
}
}
}
int[][] minDays = new int[N][M];
int[] dx = {1,0,-1,0};
int[] dy = {0,1,0,-1};
while (!queue.isEmpty()) {
Position dequeue = queue.remove();
for (int d = 0; d < 4; d++) {
int dX = dequeue.X + dx[d];
int dY = dequeue.Y + dy[d];
if ((dX >= 0 && dX < N) && (dY >= 0 && dY < M)) {
if (tomatoes[dX][dY] == 0) {
if (visited[dX][dY] == false) {
queue.add(new Position(dX, dY));
minDays[dX][dY] = minDays[dequeue.X][dequeue.Y] + 1;
visited[dX][dY] = true;
} else { // 이미 방문한 곳이면
if (minDays[dequeue.X][dequeue.Y] + 1 < minDays[dX][dY]) {
minDays[dX][dY] = minDays[dequeue.X][dequeue.Y] + 1;
queue.add(new Position(dX, dY));
}
}
}
}
}
}
int result = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (tomatoes[i][j] == 0 && visited[i][j] == false) {
System.out.println(-1);
return;
}
else if (tomatoes[i][j] == 1 || tomatoes[i][j] == 0) {
result = (minDays[i][j] > result) ? minDays[i][j] : result;
}
}
}
System.out.println(result);
return;
}
}
class Position {
int X;
int Y;
Position(int X, int Y) {
this.X = X;
this.Y = Y;
}
}
문제 해결
시간 초과 및 지저분한 코드
package ch08_BFS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class p7576 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine()); // NM
int M = Integer.valueOf(st.nextToken()); // 상자의 가로
int N = Integer.valueOf(st.nextToken()); // 상자의 세로
char[][] tomato = new char[N + 2][M + 2]; // 토마토 상자 배열 생성
// 토마토 상자 배열 값 세팅하기
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine()); // 하나의 행
for (int j = 1; j <= M; j++) {
tomato[i][j] = st.nextToken().charAt(0);
}
}
int[] dx = {1,0,-1,0}; // 우상좌하
int[] dy = {0,1,0,-1};
Queue<Position> queue = new LinkedList<>(); // 큐 생성
int[][] minDays = new int[N + 2][M +2]; // 토마토가 익기까지 최단 날짜 저장하는 배열
// int date = 0; // 결괏값
// 토마토 상자의 모든 칸을 순회
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (tomato[i][j] == '1') { // 익은 토마토이면
queue.add(new Position(i, j)); // 해당 위치를 enqueue
while (!queue.isEmpty()) { // 큐가 빌 때까지 반복
Position tmp = queue.remove(); // dequeue
for (int d = 0; d < 4; d++) { // 인접한 칸에 대해 순회
int dX = tmp.X + dx[d];
int dY = tmp.Y + dy[d];
if ((dX > 0 && dX < N + 1) || (dY > 0 && dY < M + 1)) { // 좌표 유효성 검증
if (tomato[dX][dY] == '0') { // 1. 안 익은 토마토가 있는데,
if (minDays[dX][dY] == 0) { // 1-1. 첫 방문이면
minDays[dX][dY] = minDays[tmp.X][tmp.Y] + 1; // 최단 거리 바로 저장하고
queue.add(new Position(dX, dY)); // enqueue
}
else { // 1-2. 이미 방문했으면
if (minDays[tmp.X][tmp.Y] + 1 < minDays[dX][dY]) { // 이미 저장되어 있는 최단 날짜와 비교해서,
minDays[dX][dY] = minDays[tmp.X][tmp.Y] + 1; // 최단 거리 갱신하고
queue.add(new Position(dX, dY)); // enqueue
}
}
}
}
}
}
}
}
}
int days = 0; // 결괏값
for (int i = 1; i <= N; i++) { // 토마토 상자의 모든 칸을 순회
for (int j = 1; j <= M; j++) {
if (tomato[i][j] == '0' && minDays[i][j] == 0) { // 익지 못한 토마토가 있으면
System.out.println(-1);
return;
}
else if (tomato[i][j] == '1' || tomato[i][j] == '0') { // 토마토가 존재하면
days = (minDays[i][j] > days) ? minDays[i][j] : days; // 결괏값 갱신
}
}
}
System.out.println(days);
}
}
class Position {
int X;
int Y;
Position(int X, int Y) {
this.X = X;
this.Y = Y;
}
}
시간 초과의 원인을 내 힘으로 찾아보려고 했으나, 도저히 모르겠어서 여러 문제풀이 글을 찾아보며 이 문제의 시간 초과의 해결 방법을 알아냈다.
평범하게 입출력 부분에서 해결할 수 있는 문제가 아니었다. 순회할 필요가 없는 부분까지 순회를 해버렸기 때문에 시간 초과가 발생한 것이었다.
문제가 발생한 위 코드에서는 입력을 받아 토마토 상자 배열에 값을 세팅한 후, 값이 1인 경우를 찾아내기 위해서 아래와 같이 모든 상자의 칸을 순회한다. 그러나 0인 경우는 순회할 필요가 없기 때문에 모든 칸에 대해서 반복문을 돌릴 필요가 없게 된다.
모든 칸에 대해서 반복문을 돌리지 않고 배열값이 1인 경우만 큐에 원소를 삽입한 후 BFS 작업을 진행하려면 다음과 같이 하면 된다.
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
tomatoes[i][j] = Integer.valueOf(st.nextToken());
if (tomatoes[i][j] == 1) {
queue.add(new Position(i, j));
visited[i][j] = true;
}
}
}
int[][] minDays = new int[N][M];
int[] dx = {1,0,-1,0};
int[] dy = {0,1,0,-1};
while (!queue.isEmpty()) {
Position dequeue = queue.remove();
for (int d = 0; d < 4; d++) {
int dX = dequeue.X + dx[d];
int dY = dequeue.Y + dy[d];
if ((dX >= 0 && dX < N) && (dY >= 0 && dY < M)) {
if (tomatoes[dX][dY] == 0) {
if (visited[dX][dY] == false) {
queue.add(new Position(dX, dY));
minDays[dX][dY] = minDays[dequeue.X][dequeue.Y] + 1;
visited[dX][dY] = true;
} else { // 이미 방문한 곳이면
if (minDays[dequeue.X][dequeue.Y] + 1 < minDays[dX][dY]) {
minDays[dX][dY] = minDays[dequeue.X][dequeue.Y] + 1;
queue.add(new Position(dX, dY));
}
}
}
}
}
}입력을 받아 배열에 값을 세팅하는 과정에서, 1을 만나면 바로 큐에 값을 삽입한다. 배열 값 세팅을 완료하면 큐가 빌 때까지 BFS 작업을 진행한다.
comment
풀이 날짜 : 2023/12/22 (금), 2023/12/27 (수)
231222
아직 알고리즘 초보인 내가 풀기엔 좀 어려운 문제였다. 코드로 구현하는 과정이 굉장히 오래걸리긴 했지만, 코드를 완성하고 출력값이 한 번에 제대로 나왔다는 점에서 뿌듯했다. 코드가 되게 지저분하긴 하지만 어쨌든..ㅎ
백준에 코드 제출한 결과 40% 쯤에서 시간초과가 발생했다. 내일 시간초과를 해결하고 지저분한 코드를 깔끔하게 다시 구성해서 풀어볼 계획이다.
코드로 구현을 해나가는 과정에서, 문제의 요구사항에서 놓친 부분을 하나씩 발견하게 되어서 코드를 재구성하게 되는 일이 자꾸 발생했다. 이 문제를 푸는데 오래 걸린 원인 중 하나가 바로 이 부분이다.
앞으로 문제를 읽을 때 요구사항들을 한 번에 제대로 캐치해내도록 주의해야겠다. 그리고 이 문제의 경우 예시 출력값에서도 하나의 요구사항을 얻어냈다. 이런 점들을 잊지 말고 문제를 잘~ 풀자 !
++ 입력을 받을 때 처리할 수 있는 부분은 바로 처리를 해버리자.
231227
알고리즘 문제 하나를 며칠씩이나 붙잡고 있다보니까, 계속 자괴감에 빠진다. 알고리즘 공부 진도가 너무 더디다. 앞으로 핸드폰 하는 시간 좀 줄여서 이제는 진짜 독하게 공부해야 겠다... 이번에도 말만 그러지 말길
나중에 코딩테스트 볼 때 내 자신을 칭찬하는 날이 오길 기대하면서 열심히 공부하자 !
2024년 2월 3일 (토) 복습 코드
package review;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class p7576 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken()); //가로
int N = Integer.parseInt(st.nextToken()); //세로
int[][] tomatoes = new int[N][M];
int notTomatoeNum = 0;
Queue<Point> queue = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
int[][] minDays = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
tomatoes[i][j] = Integer.valueOf(st.nextToken());
if (tomatoes[i][j] == 1) {
queue.add(new Point(j, i));
visited[i][j] = true;
minDays[i][j] = 0;
}
else if (tomatoes[i][j] == 0) {
notTomatoeNum++;
}
}
}
int[] dx = {0, 0, -1, 1};
int[] dy = {1, -1, 0, 0};
int changedTomatoeNum = 0;
int result = 0;
while(!queue.isEmpty()) {
Point dequeue = queue.remove();
for (int d = 0; d < 4; d++) {
int dX = dequeue.X + dx[d];
int dY = dequeue.Y + dy[d];
if (dX < 0 || dX >= M || dY < 0 || dY >= N) continue;
if (tomatoes[dY][dX] == 0) {
if (visited[dY][dX] == false) {
queue.add(new Point(dX, dY));
visited[dY][dX] = true;
minDays[dY][dX] = minDays[dequeue.Y][dequeue.X] + 1;
changedTomatoeNum++;
}
else { //visited[dY][dX] == true
minDays[dY][dX] = ((minDays[dequeue.Y][dequeue.X] + 1) < minDays[dY][dX])
? (minDays[dequeue.Y][dequeue.X] + 1) : minDays[dY][dX];
}
result = (minDays[dY][dX] > result) ? minDays[dY][dX] : result;
}
}
}
if (changedTomatoeNum == notTomatoeNum) {
System.out.println(result);
return;
}
else {
System.out.println(-1);
return;
}
}
}
class Point {
int X;
int Y;
Point(int X, int Y) {
this.X = X;
this.Y = Y;
}
}
develop with JOOTT