[백준] 7576번

사이트

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

7576번: 토마토

 

문제

 

분석

static int n;
static int m;
static int[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int cnt1 = 0;
static Queue<int[]> queue = new LinkedList<>();

 

- 다음과 같이 static으로 선언해주었다. 왜 했냐면 bfs() 함수로 저 변수들을 일일히 다 넘기기 번거로워서 진행했다.

- 평소 같으면 queue는 static으로 선언을 안해줬는데 이건 다음에 설명이 나온다.

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[m][n];
visited = new boolean[m][n];

for (int i = 0; i < m; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < n; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
        if (arr[i][j] == 1) {
            cnt1++;
            queue.add(new int[]{i, j});
        }
    }
}

- 입력된 수를 받고 배열에 저장하는 방식이다. 

- queue.add(new int[]{i,j})는 평소에 bfs 함수에 있어야 되지만 이번에는 1일때 동시 출발 해야되므로 넣었다. 

 

static int bfs() {
    int cnt = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int k = 0; k < size; k++) {
            int[] temp = queue.poll();
            int staticX = temp[0];
            int staticY = temp[1];
            for (int i = 0; i < 4; i++) {
                int nextX = staticX + dx[i];
                int nextY = staticY + dy[i];
                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
                    if (arr[nextX][nextY] == 0 && !visited[nextX][nextY]) {
                        visited[nextX][nextY] = true;
                        arr[nextX][nextY] = 1;
                        queue.add(new int[]{nextX, nextY});
                    }
                }
            }
        }
        cnt++;
    }
    return cnt - 1;
}

 

- 익숙한 bfs()함수를 잘보자 1일때 (x,y)위치가 큐에 저장되어 있어 처음에 그 size를 얻는다.

- 그 후 size 크기에 따라 for 구문을 동시출발을을 한다. (bfs 구문 설명은 생략! 워낙 유명하기 때문에 잘알거라고 믿는다.)

- 즉 처음 1의 위치가 (0,0) 이면 dx , dy에 따라 nextX, nextY가 결정되면서 if문에 걸리면 해당 nextX, nextY 들이 queue에 입력된다. 또 다음 1의 위치가 (3,5)이면 위랑 똑같은 방식들로 그들이 queue에 입력된다. 

- 즉 size가 핵심이다! 이것이 있어야지 동시 출발이 가능해진다. 

- 토마토가 다익기까지 걸리는 날짜를 묻는 것이므로 size for 구문 아래에다 cnt++을 넣는다. 즉 동시 출발되는 친구들끼리cnt를 세는 것이다. 

- return cnt-1 에서 -1하는 이유는 마지막 날짜도 다음 날짜로 가기 위해 cnt++이 되므로 -1을 해줘야 된다.  

 

    int result = bfs();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 0) {
                System.out.println(-1);
                return;
            }
        }
        if (i == m - 1) {
            System.out.println(result);
        }
    }
}

- bfs()에서 나온 값을 result로 지정한다. 

- 이때 바뀐 arr배열에서 0이 있으면 -1을 출력하고 return을 한다. 

- 하지만 0이 없을경우 첫번째 for 구문에서 끝자리인 m-1일때 result값을 출력하여 원하는 정답을 얻을 수 있다. 

 

전체 코드 

package graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Graph7576 {
    static int n;
    static int m;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int cnt1 = 0;
    static Queue<int[]> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1) {
                    cnt1++;
                    queue.add(new int[]{i, j});
                }
            }
        }
        int result = bfs();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
            }
            if (i == m - 1) {
                System.out.println(result);
            }
        }
    }

    static int bfs() {
        int cnt = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int[] temp = queue.poll();
                int staticX = temp[0];
                int staticY = temp[1];
                for (int i = 0; i < 4; i++) {
                    int nextX = staticX + dx[i];
                    int nextY = staticY + dy[i];
                    if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
                        if (arr[nextX][nextY] == 0 && !visited[nextX][nextY]) {
                            visited[nextX][nextY] = true;
                            arr[nextX][nextY] = 1;
                            queue.add(new int[]{nextX, nextY});
                        }
                    }
                }
            }
            cnt++;
        }
        return cnt - 1;
    }
}

 

 

결과

 

느낀점

9월 13일라 풀었던 문제였는데 틀렸다.... 그때 이후로 바빠서 못푼 문제를 지금 40분만에 다시 풀었다.. 그땐 왜 못풀었을까... 그당시 hashMap 이런걸로 적용해서 더욱더 헷갈린 문제였다. 핵심은 배열을 지정할때 1이 있을떄 그 위치를 queue로 값을 넣는 거였는데... 이로써 골드5도 무난히 해결!! 그래프가 젤 재밌고 쉽다.