백준 Q7576 - 토마토

문제 및 입출력

---

풀이

시작점이 여러개일 때 BFS를 적용시키는 문제이다

 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) {
                    startIdx.add(new int[]{i, j});

                }
            }
        }

자료형이 배열인 startIdx 리스트를 만들어서, map에서 1인 값의 좌표를 담는다

for (int i = 0; i < startIdx.size(); i++) {
	queue.add(new int[]{startIdx.get(i)[0], startIdx.get(i)[1]});
}

int day = 0;

startIdx 리스트에 있는 값을 큐에 담아준다 -> 이 과정은 한번에 처리해도 될 것 같다

while (!queue.isEmpty()) {
	int size = queue.size(); 
	for (int t = 0; t < size; t++) {
		int[] current = queue.poll();
		for (int i = 0; i < 4; i++) {
			int nextX = current[1] + dx[i];
			int nextY = current[0] + dy[i];
			if (0 <= nextX && nextX < M && 0 <= nextY && nextY < N 
            		&& map[nextY][nextX] == 0) {
				queue.add(new int[]{nextY, nextX});
				map[nextY][nextX] = 1;
			}
		}
	}
	day++;
}
return day - 1;

bfs 메서드이고, 큐 크기를 고정시켜 동적으로 변하지 않게 해야한다

위 처음 코드를 리팩토링하여 최종코드에 반영하여 작성할 것이다

---

최종 코드

public class Main {
    static int M, N;
    static int[][] map;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    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());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[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.add(new int[]{i, j});
                }
            }
        }

        bfs();

        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
                result = Math.max(result, map[i][j]);
            }
        }
        System.out.println(result - 1);
    }

    private static void bfs() {
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int t = 0; t < size; t++) {
                int[] current = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int nextRow = current[0] + dx[i];
                    int nextCol = current[1] + dy[i];
                    if(0 <= nextRow && nextRow < N && 0 <= nextCol && nextCol < M 
                    		&& map[nextRow][nextCol] == 0) {
                        queue.add(new int[]{nextRow, nextCol});
                        map[nextRow][nextCol] = map[current[0]][current[1]] + 1;
                    }
                }
            }
        }
    }
}

---

풀이 후기

처음 풀이 -> 리팩토링 과정
1. 리스트에 담는 과정을 생략하여 바로 static으로 선언한 큐에 담는다
2. 변수명 X,Y 좌표 혼란을 피하기 위해 nextRow, nextCol 과 같이 변경하였다
3. count, day 변수 등을 사용하지 않고 map[nextRow][nextCol] = map[current[0]][current[1]] + 1; 과 같이 이전노드 값에 더하는 방식으로 변경하였다