본문 바로가기
알고리즘/BFS

[백준] 토마토/자바

by 순원이 2024. 5. 12.

문제         

레벨: G5
알고리즘: BFS
풀이시간: 2시간
힌트 참조 유무: 유

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

 

1 번째 시도   

  • 기존 bfs와 다른 점은 하나인 줄 알았다. 
    • 방향이 상,하가 추가 되서 총 6개를 탐색해야 된다는 점이다 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;


public class Main {

    static int[] xx;
    static int[] yy;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");

        int L = Integer.parseInt(s[0]);
        int W = Integer.parseInt(s[1]);
        int H = Integer.parseInt(s[2]);

        boolean[][] visited = new boolean[W*H][L];
        //동,북,남,서,상,하
        xx = new int[]{1, 0, 0, -1,0,0};
        yy = new int[]{0, 1, -1, 0,H,-H};
        int[][] arr = new int[W*H][L];

        for (int i =0; i < W*H; i++) {
            String[] s2 = br.readLine().split(" ");
            for(int j =0; j < L; j++) {
                arr[i][j] = Integer.parseInt(s2[j]);
            }
        }

        Queue<int[]> q = new LinkedList<int[]>();
        int answer = 0;
        for (int i =0; i < W*H; i++) {
            for(int j =0; j < L; j++) {
                System.out.println("for 새 시작" + " i: " + i + " j: " + j);
                int cnt = 0;
                if (arr[i][j] == 1) {
                    q.add(new int[]{j,i});
                    while (!q.isEmpty()) {
                        System.out.println("while 새 시작" + " i: " + i + " j: " + j);
                        int[] now = q.poll();
                        int x = now[0];
                        int y = now[1];
                        boolean checkChange = false;

                        for(int k = 0; k < 6; k++) {
                            int nx = x + xx[k];
                            int ny = y + yy[k];
                            if(nx < 0 || nx >= L || ny < 0 || ny >= W*H)
                                continue;

                            if(visited[ny][nx] || arr[ny][nx] == 1 || arr[ny][nx] == -1)
                                continue;
                            checkChange = true;
                            System.out.println("큐에 넣는다" + nx + " " + ny);
                            arr[ny][nx] = 1;
                            q.add(new int[]{nx,ny});
                            visited[ny][nx] = true;

                        }
                        if(checkChange == true)
                            cnt++;
                    }
                }
                answer = Math.max(answer, cnt);
            }
        }

        boolean checkZero = false;
        for (int i =0; i < W*H; i++) {
            for(int j =0; j < L; j++) {
                if(arr[i][j] == 0) {
                    checkZero = true;
                    System.out.println(-1);
                    break;
                }
            }
            if(checkZero == true)
                break;
        }
        if(checkZero == false)
            System.out.println(answer);

        for (int i =0; i < W*H; i++) {
            for(int j =0; j < L; j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }
    }
}

디버깅을  위해 sout를 찍었다.

 

예제 2번을 돌려보니 틀렸다.

내코드 정답: 17

원래 정답: 4

 

익은 토마토A만 신경써서 그렇다. 익은 토마토 B도 A와 같이 다른 토마토의 영향을 주고 있어야 한다. 

 

2 번째 시도  

  • 입력값으로부터 토마토배열에 숫자를 입력할 때 숫자 1이면 큐에 집어넣는다
  • 큐 - > 우선순위 큐로 바꾸기
    • day를 신경써야 하므로 
      • 1일차 때 익은 토마토로 변한 아이들 먼저 bfs 돌리고 2일차 때 익은 토마토 bfs 돌리고 .... 계속
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;


public class Main {

    static int[] xx;
    static int[] yy;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");

        int L = Integer.parseInt(s[0]);
        int W = Integer.parseInt(s[1]);
        int H = Integer.parseInt(s[2]);

        boolean[][] visited = new boolean[W * H][L];
        //동,북,남,서,하,상
        xx = new int[]{1, 0, 0, -1, 0, 0};
        yy = new int[]{0, 1, -1, 0, H, -H};
        int[][] arr = new int[W * H][L];
        Queue<int[]> q = new PriorityQueue<int[]>((o1, o2) -> o1[2]-o2[2]);

        for (int i = 0; i < W * H; i++) {
            String[] s2 = br.readLine().split(" ");
            for (int j = 0; j < L; j++) {
                int number = Integer.parseInt(s2[j]);
                arr[i][j] = number;
                if (number == 1)
                    q.add((new int[]{j, i, 0}));
            }
        }

        int answer = 0;


        int cnt = 0;
        while (!q.isEmpty()) {
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            int day = now[2];
            answer = day;

            for (int k = 0; k < 6; k++) {
                int nx = x + xx[k];
                int ny = y + yy[k];
                if (nx < 0 || nx >= L || ny < 0 || ny >= W * H)
                    continue;

                if (visited[ny][nx] || arr[ny][nx] == 1 || arr[ny][nx] == -1)
                    continue;
                arr[ny][nx] = 1;
                q.add(new int[]{nx, ny, day+1});
                visited[ny][nx] = true;

            }
        }

        answer = Math.max(answer, cnt);


        boolean checkZero = false;
        for (int i = 0; i < W * H; i++) {
            for (int j = 0; j < L; j++) {
                if (arr[i][j] == 0) {
                    checkZero = true;
                    System.out.println(-1);
                    break;
                }
            }
            if (checkZero == true)
                break;
        }
        if (checkZero == false)
            System.out.println(answer);
    }
}

예제테스트는 다 통과했지만 정답은 아니라고 나온다.

 

2시간을 고민해봤지만 틀린 이유를 알 수 없겠다.

남의 코드  

 

내코드와 다른점

  • 토마토 배열을 3차원으로 표현
  • visited배열 사용 x
    • 0인 원소만 큐에 집어넣기 때문에 visited 필요없음
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[][][] box;
	static ArrayList<Tomato3d> list = new ArrayList<>();
	static int h, n, m;

	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()); // 행
		h = Integer.parseInt(st.nextToken()); // 높이

		box = new int[h][n][m];

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < n; j++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int k = 0; k < m; k++) {
					box[i][j][k] = Integer.parseInt(st.nextToken());                
					if (box[i][j][k] == 1) {
						list.add(new Tomato3d(i, j, k));
					}
				}
			}
		}


		int result = bfs() - 1;
		LOOP: for (int i = 0; i < h; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < m; k++) {
					if (box[i][j][k] == 0) {
						result = -1;
						break LOOP;
					}
				}
			}
		}
		System.out.println(result);


	}

	private static int bfs() {
		int z = 0, x = 0, y = 0;
		int[] az = { -1, 0, 0, 0, 0, 1 };
		int[] ay = { 0, 0, 0, -1, 1, 0 };
		int[] ax = { 0, -1, 1, 0, 0, 0, };

		Queue<Tomato3d> q = new LinkedList<>();
		for (int i = 0; i < list.size(); i++) {
			q.offer(list.get(i));
		}

		while (!q.isEmpty()) {
			Tomato3d tomato = q.poll();
			z = tomato.getZ();
			x = tomato.getX();
			y = tomato.getY();

			for (int i = 0; i < 6; i++) {
				int nz = z + az[i];
				int nx = x + ax[i];
				int ny = y + ay[i];

				if (nx >= n || ny >= m || nz >= h || nx < 0 || ny < 0 || nz < 0) {
					continue;
				}
				if (box[nz][nx][ny] == 0) {
					q.offer(new Tomato3d(nz, nx, ny));

					box[nz][nx][ny] = box[z][x][y] + 1;

				}

			}
		}

		return box[z][x][y];
	}

}

class Tomato3d {
	private int z;
	private int x;
	private int y;

	public Tomato3d(int z, int x, int y) {
		this.z = z;
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}

	public int getZ() {
		return z;
	}
}
출처: https://jumping-to-the-water.tistory.com/113 [Jumping to the water:티스토리]
저작자표시

'알고리즘 > BFS' 카테고리의 다른 글

[백준] 아기상어 / 자바  (0) 2024.05.25
[백준] 벽 부수고 이동하기/자바  (0) 2024.05.07
항해99 26일차 TIl( 단어 변환 / 프로그래머스)  (0) 2024.04.23
항해 99 25일차 TIL( 게임 맵 최단거리 / 프로그래머스)  (0) 2024.04.22

관련글

티스토리툴바