[SWEA] 1258. 행렬찾기

[ 문제 풀이 ]

1. DFS를 하면서 화학 물질이 들어있는 용기들의 좌표를 visited 에 true 로 표시해줍니다.

2. 표시했으면 용기들의 가로세로 길이를 구해야하기 때문에 다시 반복문을 처음부터 돌면서 visited 가 true인 좌표에서 좌우로 visited 가 true 인 곳을 r과 c로 체크하여 가로 세로 길이를 구하고 getLen 이라는 2차원 boolean 배열에 표시합니다. 그 이유는 다음 좌표가 이미 용기로 정해져 계산 될 경우 그 자리는 계산하지 않아도 된다는 것을 표시하기 위함입니다.

---

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Solution {
	
	
	static int  N;
	static int[][] map, dir = {{1,0},{0,1},{-1,0},{0,-1}};
	static boolean[][] visited, getLen;
	static ArrayList<Pair> list;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	
		int T = sc.nextInt();
		
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt();
			map = new int[N][N];
			visited = new boolean[N][N];
			list = new ArrayList();
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			
			int count = 0;
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(visited[i][j] || map[i][j] == 0) continue;
					DFS(i, j);
					count++;
				}
			}
			
			
			getLen = new boolean[N][N];
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(getLen[i][j]) continue;
					if(!visited[i][j]) continue;
					else {
						
						int r = 0;
						int c = 0;
						while(true) {
							r++;
							if(i+r < N && visited[i+r][j] == true) {
								
							} else break;
						}
						while(true) {
							c++;
							if(j+c < N && visited[i][j+c] == true) {
								
							} else break;
						}
						
						for(int k=i; k<i+r; k++) {
							for(int l=j; l<j+c; l++) {
								getLen[k][l] = true;
							}
						}
						
						list.add(new Pair(r, c, r*c));
					}
				}
			}
			
			Collections.sort(list);
			System.out.print("#" + tc + " " + count + " ");
			for(int i=0; i<list.size(); i++) {
				System.out.print(list.get(i).x + " " + list.get(i).y + " ");
			}
			System.out.println();
			
		}
		
		
	}
	
	public static void DFS(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			
			if(isInside(nx, ny) && !visited[nx][ny] && map[nx][ny] != 0) {
				DFS(nx, ny);
			}
		}
		
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && x<N && y>=0 && y<N; 
	}
}

class Pair implements Comparable<Pair>{
	int x;
	int y;
	int mul;
	
	Pair(int x, int y, int mul){
		this.x=x;
		this.y=y;
		this.mul = mul;
	}
	
	@Override
	public int compareTo(Pair p) {
		if(this.mul < p.mul) return -1;
		else if(this.mul == p.mul) {
			if(this.x < p.x) return -1;
		}
		return 1;
	}
}