찰떡개발자 코딩

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

풀이 :

좌표 문제는 처음 접해봤다... 2차원 배열을 써야되겠는건 알겠는데 쉽지 않았다...

먼저 어떻게 풀어야될지 감이 안잡혔다.

너비 우선탐색 BFS를 생각해보니 Queue를 써야겠구나 싶었다.

방법

1). 우선 익은 토마토의 기준으로 안익은토마토를 익히는걸 중점적으로 생각했다.

그래서 익은 토마토의 위치를 Queue에 담아놓고 익은토마토를 한바퀴돌면서 주변의 안익은 토마토를 익히는 방식을 채택하였다.

2). 동,서,남,북을 현재 좌표기준 -1 0 +1 이런식으로 배열에 정리해놓고 가져다가 썼다.

3). 중요한점은 동서남북의 좌표를 기준으로 Tomato배열에서 체크를 했는데, 

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

이 사각형을 벗어날수도 있다는것이다.! index out of bounce... 놓쳤었다..

그래서 if (ty < 0 || tx < 0 || ty >= N || tx >= M || tomato[ty][tx] != 0)continue; 이식이 생겨나게되었다.

4). 안익은토마토를 익히고, 익은 토마토 Queue에 다시 담아주어 다시금 익힌토마토 기준으로 주변 토마토를 익혔다.

public static void main(String[] args) throws IOException {

		//토마토 => 좌표
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int M = Integer.parseInt(st.nextToken());//6
		int N = Integer.parseInt(st.nextToken());//4

		//익은 토마토 위치 queue
		Queue<int[]> queue = new LinkedList<int[]>();
		//토마토 위치 배열
		int[][] tomato = new int[N][M];//4*6
		//안익은 토마토 갯수 및 경과일
		int cnt=0, days=0;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				 tomato[i][j] = Integer.parseInt(st.nextToken());
				 if(tomato[i][j]==1) {
					 queue.offer(new int[] {i,j});
				 }else if(tomato[i][j]==0) {
					 cnt++;//안익은 토마토 갯수 체크를 위해 추가
				 }
			}
		}

		int[] x = {-1,1,0,0};
		int[] y = {0,0,-1,1};

		while(cnt>0&& !queue.isEmpty()) {
			for (int s = queue.size(); s>0; s--) {
				int[] tmp = queue.poll();
				//익은 토마토기준 근처 토마토 체크 및 익히기.
				for (int i = 0; i < 4; i++) {
					int tx = tmp[1]+x[i];
					int ty = tmp[0]+y[i];

					//익은 토마토거나 없으면? ->
					//if(tomato[tx][ty]!=0 || tx<0 || ty<0) { continue; }
					if (ty < 0 || tx < 0 || ty >= N || tx >= M || tomato[ty][tx] != 0)continue;

					//안익은 토마토면? cnt 빼고
					cnt--;
					tomato[ty][tx] =1; //-> 익히고
					queue.offer(new int[] {ty,tx});// 익은토마토라고해서 queue에 넣어주고
				}

			}
			days++;
		}
		//큐에있는것 : 익은 토마토 : 다돌면 하루
		//다익으면 경과일, 다익지 못하는 상황이면 -1 출력
		System.out.println(cnt==0? days : -1);
	}