SWEA[1258] - 행렬찾기[D4]

링크

SWEA[1258]

문제설명

• 시뮬레이션

문제풀이

• 시뮬레이션

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution1258 {
    public static int[][]map;
    public static int r;
    public static int c;
    public static int N;
    public static int Cnt=0;
    public static void Search(int[]rc) {
        r=1;
        c=1;

        int sr=rc[0];
        int sc=rc[1];
        int nr=0;
        int nc=0;
        while(true) {
            nr = sr+1;
            nc = sc;
//            경계안이고, 화학물질이 있을 경우
            if(nr>=0 && nr<N && map[nr][nc]!=0) {
                r++;
                sr=nr;
            }
            else{
                nr--;
                break;
            }
        }
        while(true) {
            nr = sr;
            nc = sc+1;
//            경계안이고, 화학물질이 있을 경우
            if(nc>=0 && nc<N && map[nr][nc]!=0) {
                c++;
                sc=nc;
            }
            else{
                nr--;
                break;
            }
        }
    }
    public static LinkedList<int[]> ans = new LinkedList<>();
    public static void main(String args[]) throws Exception
    {
        System.setIn(new FileInputStream("res/swea/1258.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T;
        T=Integer.parseInt(br.readLine());

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = Integer.parseInt(br.readLine().trim());
            map = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j]=Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][j]!=0) {
                        Cnt++;
                        Search(new int[] {i,j});    //r,c 갱신
                        ans.add(new int[] {r,c});
//                        탐색한 사각형 삭제
                        for (int i_ = 0; i_ < r; i_++) {
                            for (int j_ = 0; j_ < c; j_++) {
                                map[i+i_][j+j_]=0;
                            }
                        }
                    }
                }
            }

            Collections.sort(ans,new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    // TODO Auto-generated method stub
                    if(o1[0]*o1[1]!=o2[0]*o2[1]) {
                        return (o1[0]*o1[1]-o2[0]*o2[1]);
                    }
                    else{
                        return o1[0]-o2[0];
                    }
                };
            });

            System.out.print("#"+test_case+" "+Cnt+" ");
            for (int i = 0; i < ans.size(); i++) {
                System.out.print(ans.get(i)[0]+" "+ans.get(i)[1]+" ");
            }
            System.out.println();
            //초기화
            ans.clear();
            Cnt=0;
        }
    }
}

아쉬운점

• r만탐색, c만탐색한다고 {r,c} 동시에 고려하지 못했음
  • r기준으로 아래로 탐색 할 때, 탐색이 끝나면 최대거리 +1을 반납하여 c를 탐색할 때, 무조건 경계검사에서 false 뜬다.
    • 경계검사끝나면 r,c 초기 지점으로 이동
    • c검사할때도 똑같음
• 문제 정렬 조건을 제대로 안읽었음
  • 행렬의 곱의 값이 같은 경우는 행의 크기를 기준으로 정렬한다.

잘한점

• 디버깅실력이 늘고있다(?)
• 화학물질을 제거함으로써 다시 탐색하는경우의 수는 없앴음.

다른풀이

• 가로로는 +1
• 세로로는 +100 씩해서 값을 parsing해서 r*c 구할 수 있음.