FIRE

문제 복기

• 잘한 부분

불이 번지는 좌표 조건과 상근이가 이동하는 좌표 조건은 정확하게 맞았다!

• 틀린 이유

-문제 잘못 이해함 : 1초가 지날 때마다 상근이만 이동하는 것으로 생각하고, 불의 초기 위치와 상하좌우 인접노드만 이동불가능한 위치로 처리해주었다. - 최소 시간을 출력하는데 2차원 배열로 시간을 기록해버렸다. 정답의 차원조차 헷갈린 것이다. 빙하 문제와 마찬가지로, 주어진 Map 데이터가 시간에 따라 변화하고, 문제에서 주어지는 조건을 만족하기까지 걸리는 최소 시간을 구하는 것이기 때문에 정답은 정수가 되어야한다! - Scanner와 BufferedReader를 섞어쓰니까 테스트케이스가 거듭될수록 br로 받는 숫자를 인식하지 못하는 것 같다! => 그러므로 Scanner 쓸 땐 Scanner만, BufferedReader 쓸 땐 BufferedReader만 쓰도록 한다!

• 알고리즘 생각 1. 일단 상근이가 이동 불가능한 위치, 이동 가능한 위치 를 생각해본다. 이동 X : 벽(#),불(*),불이 붙을 위치(상하좌우 인접좌표) 이동 O : '.' 탈출 성공 : map 범위 벗어날 때. 2. 1초 후 불,상근 위치 업데이트해야한다 2-1. escape(상근) 2-2. spread(불) 현재 불 위치와 불이 붙을 위치(상하좌우 인접좌표)로는 이동하지 못하기 때문에 불 위치를 먼저 업데이트준다! =>큐 하나에 불,상근,불,상근,..순서로 넣고 각각의 위치를 업데이트해준다!

1. 상근이의 위치를 이동시키는 함수 escape 구현 일반 bfs 구현하듯이 (x,y)에 대해 범위&중복 체크 후 큐에 (nx,ny) 넣는다. 다만 불의 위치를 먼저 처리해주기 위해 큐에 상근이 현위치를 넣기 전에 불 위치를 넣는다. 불 위치는 어떻게 큐에 넣으며 위치를 업데이트할 수 있을까? 일단 상근이 위치(x,y)를 큐에 넣기 전에 (-1,-1)을 먼저 넣어준다. 큐에서 꺼낸 좌표가 (-1,-1)이면 이것은 불을 의미하고, 불 위치를 업데이트하는 함수 spread를 호출, 실행한다. 큐가 비지 않았으면 탈출하려는 상근이 좌표가 아직 남아있다는 뜻이므로, (-1,-1)을 다시 큐에 넣어준다. 큐가 비지 않았으면 탈출하려는 상근이 좌표가 아직 남아있으므로, 상근이 좌표 뒤에 다시 (-1,-1)을 넣어주어 불 위치 업데이트해주어야한다! (상근이 위치에서 다음 좌표가 범위 밖이면 탈출 성공이고, 그렇지 않으면 계속 해서 다음좌표가 추가될 것이기 때문에 반복해서 불 위치 업데이트 먼저 해주기 위해 (-1,-1) 큐에 넣어주는 것이다.)

public static void escape(int x,int y) {//@위치부터 시작해서 map 범위를 벗어날 때까지 걸리는 시간을 리턴.
		Queue<position2> q = new LinkedList<>();
		q.add(new position2(-1,-1));
		q.add(new position2(x,y));
		visit[x][y] = true;
		int time = 0;
		while(!q.isEmpty()) {//상근이의 다음이동을 담당하는 escape순회 루프.      상근이는 map의 범위밖으로 가야한다!
			position2 cur = q.remove();
			if(cur.x==-1 && cur.y==-1) {
				spread();
				if(!q.isEmpty()) {q.add(cur);}
				time++;//불 먼저 번지고,
				continue;//다음 상근이 이동시킨다!!!
			}
			for(int i=0;i<4;i++) {//상근이의 다음 위치 next(nx,ny)
				int nx = cur.x+dx[i];
				int ny = cur.y+dy[i];
				if(nx<0 || nx>h-1 || ny<0 || ny>w-1) {//정답이 되는 조건.  (탈출 : 다음 이동 좌표가 map의 범위밖)
					sb.append(time+"\n");
					return;
				}
				if(map[nx][ny]=='.' && !visit[nx][ny]) {//이동할 수 있는 경우 : .이고, 방문하지 않은 노드일 때.
					q.add(new position2(nx,ny));
					visit[nx][ny] = true;
				}
			}
		}
		sb.append("IMPOSSIBLE\n");
	}

2. 불의 위치를 업데이트하는 spread 함수

불바다를 만들어버렸다. 기존의 코드 : 완전탐색을 해버려서 이동가능한 모든 좌표를 *으로 업데이트해버렸다.

수정 : 현재 불의 갯수를 기억해서, 딱 그 갯만큼만 bfs를 하고, 불로 만들 인접좌표를 fire 큐에 넣어준다! 수정 후 코드

public static void spread() {
		//불인 좌표를 찾아서 인접 상하좌우 좌표 불로 만들어준다.
		//fire 큐에 있는좌표 하나씩 꺼내서 상하좌우 탐색, 상하좌우 인접노드 *로 바꿔준다!
		//불바다 만들기 싫으면 초기 불좌표만큼만 불로 만든다!
		int size = fire.size();
		for(int i=0;i<size;i++) {//현재 불 갯수만큼만 번진다!예를들어 불 갯수가 1개면.1번만 그 좌표의 인접노드 큐에 추가.
			position2 cur = fire.remove();
			for(int j=0;j<4;j++) {//상근이의 다음 위치 next(nx,ny)
				int nx = cur.x+dx[j];
				int ny = cur.y+dy[j];
				if(nx<0 || nx>h-1 || ny<0 || ny>w-1) continue;
				if(map[nx][ny]=='.'||map[nx][ny]=='@') {//이동할 수 있는 경우.불이 번질 수 있는 조건.
					map[nx][ny] = '*';
					fire.add(new position2(nx,ny));
				}
			}
		}
	}

• 빠른 입,출력 Tip! 여러개의 TC에 대해 각 TC마다 정답출력해야할 때 StringBuilder를 이용하면 정답들을 모아모아서 한번에 출력하니 빠르다!