문제

토마토

풀이

배열에 있는 모든 항목들이 -1을 제외하고 전부 1이 되는 일자를 구하는 것이다
풀다가 말았던 흔적이 있어서 코드를 조금 수정해서 맞았다. 백준 제출할때 자꾸 main을 고치지 않고 작성해서 한번틀림 익숙해졌다고 생각했는데 종종 이런다

이 문제에서 1의 값에서 가장 멀리 떨어진 값에 해당하는 값이 바로 정답이 되겠다. bfs로 풀어주기 위해서 distance 2차 배열을 먼저 선언해주기로 한다. 이때 -1로 전부 초기화 해준다.

int[][] distance = new int[m][n];
for (int i = 0 ; i < m; i++) [
	Arrays.fill(distance[i], -1);
}

우선 bfs의 시작점은 익은 토마토의 동서남북방향으로 옮겨가게 됨으로 1이 되는 방향들을 전부 검사해주면 된다. 그래서 1이 되는 토마토의 방향들을 큐에 전부 넣어주면 된다. 그리고 배열의 크기 또한 유념해야 된다 (m * n) 으로 배열을 정해줘야 한다

Queue<Pair> q = new LnkedList();
for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
    	...
    	if (map[i] == 1) {
        	q.add(new Pair(i, j));
            distance[i][j] = 0;
        }
    }
}

그리고 동서남북의 방향을 가리키는 dx, dy 의 배열을 기계 처럼 먼저 선언해준다. 이쯤 되면 그냥 라이브러리에 자동으로 넣어주면 좋을 것 같기도 하다. bfs의 단점 공간복잡도 증가

int dx = {0, 0, -1, 1}
int dy = {-1, 1, 0, 0}

이제는 bfs의꽃 while문을 작성한다

while(!q.isEmpty()) {
	Pair p = q.poll();
    for (int i =0 ;i < 4; i++) {
    	int nx = p.x + dx[i];
        int ny = p.y + dy[i];
        // 범위 안에 있으면서
        // 아직 익지 안은 토마토 이고 아직 접근한적 없는 곳이어 햔다
        if (nx >= 0 && ny >= 0 && nx < m && ny < n 
        	&& map[nx][ny] = 0 && distsance[nx][ny] = -1) {
        	q.add(new Pair(nx, ny));
            distance[nx][ny] = distance[p.x][p.y] + 1;
        }
    }
}

이 다음 코드는 또 한번 더 이중 for문으로 가장 큰 숫자를 업데이트 하고 있긴한데 이거 옛날 코드라서 그런거고

사실 상위의 while 문 안에서 갱신해주면 더 빠를것같다

그리고 만약 -1이 아직도 남아있을 지도 모르기 때문에 한번더 검사를 해주는 루틴을 거친다

전체 코드

전체 코드