[SWEA] #1258 - 행렬찾기

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18LoAqItcCFAZN 

SW Expert Academy

 

💡 문제

---

[설명]

창고에는 화학 물질 용기 n^2개가 n x n으로 배열되어 있었다.

유엔 조사단은 각 용기를 조사하여 2차원 배열에 그 정보를 저장하였다.

빈 용기에 해당하는 원소는 ‘0’으로 저장하고, 화학 물질이 들어 있는 용기에 해당하는 용기는 화학 물질의 종류에 따라 ‘1’에서 ‘9’ 사이의 정수를 저장하였다.

유엔 조사단은 화학 물질이 담긴 용기들로부터 3가지 사항을 발견하였다.

1. 화학 물질이 담긴 용기들이 사각형을 이루고 있다. 또한, 사각형 내부에는 빈 용기가 없다.

예를 들어, 위의 그림에는 3개의 화학 물질이 담긴 용기들로 이루어진 사각형 A, B, C가 있다.

2. 화학 물질이 담긴 용기들로 이루어진 사각형들은 각각 차원(가로의 용기 수 x 세로의 용기 수)이 다르다.

예를 들어, 위의 그림에서 A는 (3 x 4), B는 (2 x 3), C는 (4 x 5)이다.

3. 2개의 화학 물질이 담긴 용기들로 이루어진 사각형들 사이에는 빈 용기들이 있다.

예를 들어, 위의 그림에서 A와 B 사이와 B와 C 사이를 보면, 빈 용기를 나타내는 ‘0’ 원소들이 2개의 사각형 사이에 있는 것을 알 수 있다.

단, A와 C의 경우와 같이 대각선 상으로는 빈 용기가 없을 수도 있다.

주어진 테스트 케이스에 대해 행렬을 찾는 프로그램을 작성하시오.

출력은 행렬의 개수, 행렬의 행과 열을 크기(행 X 열)가 작은 순서대로 한다.

크기가 같다면 행의 크기가 작은 순서를 먼저 출력한다.

 

💡 아이디어

---

행렬을 처음부터 끝까지 살펴보다가 0이 아닌 숫자가 나오면 이 지점이 사각형의 시작점이라고 볼 수 있다.

시작점에서부터 우측과 아래 측을 탐색하다가 우측이 인덱스를 벗어나거나 0이고, 아래 측이 인덱스를

벗어나거나 0이면 마지막 사각형의 끝 지점에 도착했다는 것을 알 수 있다.

그럼 시작점과 끝 지점을 통해 행과 열을 구할 수 있다.

그리고 이미 방문한 곳은 다시 방문하지 않게 표시를 해두면 된다.  

 

💡 소스코드

---

기존 코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;
 
class Pos implements Comparable<Pos> {
    int row;
    int col;
    int mult;
 
    Pos(int row, int col, int mult) {
        this.row = row;
        this.col = col;
        this.mult = mult;
    }
 
    @Override
    public int compareTo(Pos o) {
        if (this.mult < o.mult)
            return -1;
        else if (this.mult == o.mult) {
            int tempR = this.row;
            int tempC = this.col;
            this.row = o.row;
            this.col = o.col;
            o.row = tempR;
            o.col = tempC;
            return 0;
        } else if (this.mult > o.mult)
            return 1;
        return 0;
    }
}
 
public class Solution {
    static int N;// 2차원 배열의 크기
    static int map[][];// 입력받을 2차원 배열
    static boolean visited[][];// 방문한 곳을 나타내는 배열
    static int[] dx = { 1, 0 };// 하, 우
    static int[] dy = { 0, 1 };
    static int cnt;
    static ArrayList<Pos> result;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer sz;
        int T = Integer.parseInt(br.readLine());
 
        for (int TC = 1; TC <= T; TC++) {
            N = Integer.parseInt(br.readLine());
 
            init();
 
            // 2차원 배열에 값 저장
            for (int i = 0; i < N; i++) {
                sz = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++)
                    map[i][j] = Integer.parseInt(sz.nextToken());
            }
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] > 0 && visited[i][j] == false)
                        solve(i, j);
                }
            }
 
            System.out.print("#" + TC + " " + cnt + " ");
            Collections.sort(result);
            for (Pos p : result) {
                System.out.print(p.row + " " + p.col + " ");
            }
            System.out.println("");
        }
        br.close();
    }
 
    public static void init() {
        map = new int[N][N];
        visited = new boolean[N][N];
        cnt = 0;
        result = new ArrayList<>();
    }
 
    public static void solve(int x, int y) {
        Stack<Pos> stack = new Stack<>();
        int curX = 0, curY = 0;
 
        // 시작점 stack에 push
        stack.push(new Pos(x, y, 0));
 
        while (!stack.isEmpty()) {
            Pos p = stack.pop();
            curX = p.row;
            curY = p.col;
            visited[curX][curY] = true;
 
            // 오른쪽이 0이거나 벽이고, 아래가 0이거나 벽일 때
            if ((map[curX][curY + 1] == 0 || curY + 1 >= N) && (map[curX + 1][curY] == 0 || curX + 1 >= N))
                break;
 
            for (int i = 0; i < 2; i++) {
                int nx = curX + dx[i];
                int ny = curY + dy[i];
 
                if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                    continue;
                else if (map[nx][ny] > 0 && visited[nx][ny] == false)
                    stack.push(new Pos(nx, ny, 0));
            }
        }
 
        for (int i = x; i <= curX; i++)
            for (int j = y; j <= curY; j++)
                visited[i][j] = true;
 
        int row = Math.abs(x - curX) + 1;
        int col = Math.abs(y - curY) + 1;
 
        result.add(new Pos(row, col, row * col));
        cnt++;
    }
}

수정 코드

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

class Pos implements Comparable<Pos> {
	int row;
	int col;
	int mult;

	Pos(int row, int col, int mult) {
		this.row = row;
		this.col = col;
		this.mult = mult;
	}

	@Override
	public int compareTo(Pos o) {
		if (this.mult < o.mult)
			return -1;
		
		// 행 X 열을 했을 때 값이 같으면 교체해준다.
		// Collections.sort를 특정 기준으로 정렬하기 위함
		else if (this.mult == o.mult) {
			if (this.row < o.row) {
				int tempRow = this.row;
				int tempCol = this.col;
				this.row = o.row;
				this.col = o.col;
				o.row = tempRow;
				o.col = tempCol;
			}
			return 0;
		} 
		else 
			return 1;
	}
}

public class P_1258 {
	static int N;// 2차원 배열의 크기
	static int map[][];// 입력받을 2차원 배열
	static boolean visited[][];// 방문한 곳을 나타내는 배열
	static int cnt;
	static ArrayList<Pos> result;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("P1258_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sz;
		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			N = Integer.parseInt(br.readLine());

			init();

			// 2차원 배열에 값 저장
			for (int i = 0; i < N; i++) {
				sz = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++)
					map[i][j] = Integer.parseInt(sz.nextToken());
			}

			// 배열의 처음부터 끝을 살펴보며 0보다 크고 방문하지 않은 곳은
			// solve() method 호출
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] > 0 && visited[i][j] == false)
						solve(i, j);
				}
			}

			System.out.print("#" + TC + " " + cnt + " ");
			Collections.sort(result);
			for (Pos p : result) {
				System.out.print(p.row + " " + p.col + " ");
			}
			System.out.println("");
		}
		br.close();
	}

	//초기화
	public static void init() {
		map = new int[N][N];
		visited = new boolean[N][N];
		cnt = 0;
		result = new ArrayList<>();
	}

	public static void solve(int x, int y) {//x와 y는 행렬의 시작점
		int nx = x;
		int ny = y;

		// 우선 행의 끝을 찾아주고
		while (true) {
			if (ny >= N)
				break;

			else if (map[nx][ny] == 0)
				break;

			ny++;
		}
		ny -= 1;

		// 열의 끝을 찾아준다.
		while (true) {
			if (nx >= N)
				break;

			else if (map[nx][ny] == 0)
				break;

			nx++;
		}
		nx -= 1;

		// 그럼 시작점(x, y)와 마지막 지점 (nx, ny)를 통해 행렬의 크기를 구할 수 있다.
		int row = Math.abs(nx - x) + 1;
		int col = Math.abs(ny - y) + 1;

		// 그리고 방문한 곳을 표시해준다.
		for (int i = x; i <= nx; i++)
			for (int j = y; j <= ny; j++)
				visited[i][j] = true;

		// 결과는 result에 추가하고
		result.add(new Pos(row, col, row * col));
		
		// 개수를 늘려준다.
		cnt++;
	}
}

 

💡 결과

---

이 문제를 해결하는데 처음엔 4방 탐색을 이용했다.

하지만, 사각형의 왼쪽 위 모서리에서 시작한다면 우측과 아래 측만 보면 된다고 생각했다.

이후 새로운 아이디어가 떠올라 코드를 수정했다.

우선 시작점에서 행의 끝을 찾고, 열의 끝을 찾아 행렬의 마지막 지점을 찾았다. 

또한, ArrayList를 특정 기준으로 Collections.sort() 하기 위해선 compareTo를 Override 해서

사용하면 된다는 것을 알 수 있었다.