[백준] 16946 - 벽 부수고 이동하기 4

[문제링크]

16946번: 벽 부수고 이동하기 4

 

0. 사방 처리를 위해 외곽을 1로 감쌌다

 

1. 전체를 탐색하면서 0, 빈공간을 만날 경우 BFS 진행

  - BFS에서 거쳐가는 모든 칸을 index로 칠해 재탐색 방지 + 추후 이용

  - BFS의 결과로 반환된 size를 ArrayList에 저장한다

  - ( 0은 빈칸, 1은 벽이므로 area index는 2부터 시작, index 유지를 위해 0 2개 삽입)

 

2. 전체를 탐색하면서 벽을 만날 경우 4방향에 대해

  - 1이 아니면 빈 공간이 index로 칠해진 것. 해당 index의 size를 ArrayList로부터 가져와 누적한다.

  - 1이면 벽, 무시한다

 

3. 각 방향의 area index가 같다면, 두번 더해선 안된다.

  - 4개의 값이므로, 각각 이전 값들과 다를 경우에만 누적한다 ( 가독성, 확장성은 좋지 않지만, 성능 효율적 )

  - set에 다 던져넣고 하나씩 꺼내며 쓴다 ( 가독성, 확장성은 좋지만, 성능 비효율적)

 

4. 출력할 때 println등을 이용하면 최악 1000*1000번 출력하게되므로, buffer 이용이 필수적이다

 

+ 4번 print구간은 3번 반복문에 그대로 삽입할 수 있다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		map=new int[n+2][m+2];
		int[][]ansMap=new int[n+2][m+2];
		//외곽 padding
		for (int i = 0; i < n+2; i++) {
			map[i][0]=1;map[i][m+1]=1;
		}
		for (int i = 0; i < m+2; i++) {
			map[0][i]=1;map[n+1][i]=1;
		}
		// 1. input
		for (int i = 1; i <= n; i++) {
			String s = br.readLine();
			for (int j = 1; j <= m; j++) {
				map[i][j]=s.charAt(j-1)-'0';
			}
		}
		//2. get size by bfs for each area + tagging
		ArrayList<Integer>area=new ArrayList<>();
		area.add(0);area.add(0);
		int idx=2;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(map[i][j]==0) {
					int size=search(idx++, i, j);
					area.add(size);
				}
			}
		}
		//3. check four-dir of each wall + add if area
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(map[i][j]==1) {
					ansMap[i][j]+=1;
					if(map[i+1][j]!=1)
						ansMap[i][j]+=area.get(map[i+1][j]);
					if(map[i][j+1]!=1 && map[i+1][j]!=map[i][j+1])
						ansMap[i][j]+=area.get(map[i][j+1]);
					if(map[i-1][j]!=1&& map[i+1][j]!=map[i-1][j] && map[i-1][j]!=map[i][j+1])
						ansMap[i][j]+=area.get(map[i-1][j]);
					if(map[i][j-1]!=1 && map[i][j-1]!=map[i+1][j]&& map[i][j-1]!=map[i][j+1] && map[i][j-1]!=map[i-1][j])
						ansMap[i][j]+=area.get(map[i][j-1]);
				}
			}
		}
		//4.print
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < m+1; j++)sb.append(ansMap[i][j]%10);
			sb.append("\n");
		}System.out.println(sb);
	}
	static int[][]map;
	static int search(int idx, int x, int y) {
		int size=1;
		map[x][y]=idx;
		if(map[x+1][y]==0)size+=search(idx,x+1,y);
		if(map[x-1][y]==0)size+=search(idx,x-1,y);
		if(map[x][y+1]==0)size+=search(idx,x,y+1);
		if(map[x][y-1]==0)size+=search(idx,x,y-1);
		return size;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면 ( Hashset 미사용/사용 )