728x90
문제
https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
풀이
토마토가 다 익는데까지 며칠이 걸렸는지 출력하는 문제이기 때문에 DFS로 풀면 답을 찾기 힘들 것이다. 그래서 BFS로 풀었음!
1번 방법(오답)
BFS할 때 사용하는 큐<Tomato>의 Tomato 클래스는 익은 토마토의 위치와 며칠째에 익었는지를 나타내는 day를 멤버변수로 함!
큐에서 하나씩 빼서 다음 칸으로 갈 수 있는지 검사하며, 다음 칸을 큐에 넣어줄 때 day+1을 하면서 넣어줬음.
그리고 마지막으로 큐에 들어간 Tomato 클래스의 day를 뽑아주면...!
답인줄 알았는데 왜인지 모르게 답이 아니었음 ㅠ
그래서 백준에도 질문을 올려놓긴 함 ㅋㅋㅋㅋㅋ
암튼 그래서 2번 방법으로 풀었음!
2번 방법(정답)
위랑 크게 크게는 비슷함. BFS로 탐색하였음.
다른 점은 Tomato 클래스에 day라는 멤버변수를 없애고, map[][]에 그냥 1씩 증가하면서 탐색을 해주고 그걸 day라고 생각함!
그렇게 해서 BFS가 다 끝나면 마지막에 getMax()를 이용해서 map[][]에서 최댓값(토마토가 다 익는데에 걸린 시간)을 찾아서 출력해줌!
결론
맞추긴 했는데 내 생각엔 1번 풀이가 더 이쁜 것 같은데 정답이 아니라고 나와서 의문이였음 어디가 틀렸는지 아직도 모르겠음 ㅠ
오답 코드, 정답 코드 둘 다 주석은 달아놨으니까 자세한건 주석 참고!!
오답 코드
// 7576번 토마토
// https://www.acmicpc.net/problem/7576
package BAEKJOON;
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 Num7576_토마토_오답 {
static int N, M;
static int[][] map;
static boolean[][] visited;
static Queue<Tomato> queue = new LinkedList<>();
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
private static class Tomato {
int r;
int c;
int day;
public Tomato(int r, int c, int day) {
this.r = r;
this.c = c;
this.day = day;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 1) {
queue.offer(new Tomato(i, j, 0));
}
}
}
int day = 0;
// bfs 끝날 때까지 반복
while (!queue.isEmpty()) {
day = queue.peek().day; // day 갱신
solution();
}
// for (int i = 0 ;i < N; i++) {
// System.out.println(Arrays.toString(map[i]));
// }
// System.out.println();
if (isFail()) {
System.out.println(-1);
} else {
System.out.println(day);
}
}
// bfs 함수
private static void solution() {
Tomato temp = queue.poll();
int r = temp.r;
int c = temp.c;
int day = temp.day;
if (visited[r][c]) {
return;
}
visited[r][c] = true; // 방문 체크
map[r][c] = 1; // 익은 토마토로 만들어줌
for (int i = 0; i < 4; i++) { // 사방 탐색
int nr = r + dr[i];
int nc = c + dc[i];
// 범위 밖이면 continue
if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
continue;
}
// 다음으로 갈 수 있는 칸이면 큐에 넣어줌(day 증가시켜서)
if (map[nr][nc] == 0 && !visited[nr][nc]) {
queue.offer(new Tomato(nr, nc, day + 1));
}
}
}
// map에 0(익지 않은 토마토)가 있으면 return true
private static boolean isFail() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
return true;
}
}
}
return false;
}
}
정답 코드
// 7576번 토마토
// https://www.acmicpc.net/problem/7576
package BAEKJOON;
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 Num7576_토마토 {
static int N, M;
static int[][] map;
static boolean[][] visited; // 방문 체크 배열
static Queue<Tomato> queue = new LinkedList<>();
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
private static class Tomato {
int r;
int c;
public Tomato(int r, int c) {
this.r = r;
this.c = c;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M];
// 입력
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 1) { // 익은 토마토면 넣어줌 (시작점)
queue.offer(new Tomato(i, j));
}
}
}
// bfs (큐에 아무것도 없을 때까지)
while (!queue.isEmpty()) {
solution();
}
int max = 0;
if (isFail()) { // 토마토가 다 익지 못하면 -1 출력
System.out.println(-1);
} else { // 토마토가 다 익으면 며칠 걸려서 다 익었는지 출력
System.out.println(getMax(max));
}
}
// bfs
private static void solution() {
Tomato temp = queue.poll();
int r = temp.r;
int c = temp.c;
if (visited[r][c]) {
return;
}
visited[r][c] = true; // 방문 체크
for (int i = 0; i < 4; i++) { // 사방 탐색
int nr = r + dr[i];
int nc = c + dc[i];
// 범위 밖으로 벗어나면 continue
if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
continue;
}
// 이동할 수 있는 칸이면 day를 하루 증가해서 저장하고 큐에 추가해줌
if (map[nr][nc] == 0 && !visited[nr][nc]) {
map[nr][nc] = map[r][c] + 1;
queue.offer(new Tomato(nr, nc));
}
}
}
// map에 0(익지 않은 토마토)가 있으면 return true
private static boolean isFail() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
return true;
}
}
}
return false;
}
// 며칠 걸려서 토마토가 다 익었는지 알아내는 함수
private static int getMax(int max) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (max < map[i][j]) {
max = map[i][j];
}
}
}
// 걸린 일수는 max에서 1 빼줘야 함
return max - 1;
}
}728x90