(JAVA) 백준 10026번 : 적록색약

https://www.acmicpc.net/problem/10026

10026번: 적록색약

맞다... 이번에 더글로리 시즌 2까지 다 보고 이 문제 제목보니 도저히 지나칠수 없었다..

 

첫번째 시도 (실패)

import java.io.InputStreamReader;
import java.io.BufferedReader;
 
 
public class B_10026 {
    static boolean[][] vis;
    static int N;
    static char[][] G,D;
    static int[][] dic = {{1,0},{0,1},{-1,0},{0,-1}};
    static boolean check(int a , int b) {
        if  (a>=N||a<0) return false;
        if (b>=N||b<0) return false;
        return true;
    }
    static void bfs(int a,int b,char[][] G) {
        char k = G[a][b];
        int[][] que = new int[100000000][2];
        int front=0,rear=0;
        que[rear][0]=a;que[rear++][1]=b;
        vis[a][b] = true;
        while(front!=rear) {
            int x=que[front][0],y=que[front++][1];
            for (int i=0;i<4;i++) {
                int nx=x+dic[i][0],ny=y+dic[i][1];
                if (check(nx,ny)==true) {
                    if (G[nx][ny]!=k) continue;
                    if (vis[nx][ny]==true) continue;
                    que[rear][0]=nx;que[rear++][1]=ny;
                    vis[nx][ny]=true;
                }
            }
        }
    }
    static int Ans(char[][] G) {
        int h=0;
        for (int i=0;i<N;i++) 
            for (int j=0;j<N;j++) 
                if (vis[i][j]!=true) { 
                    bfs(i,j,G); h+=1;
                }
 
        return h;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        G = new char[N][N];D = new char[N][N];
        vis = new boolean[N][N];
        for (int i=0;i<N;i++) {
            String t = br.readLine();
            for (int j=0;j<N;j++) {
                G[i][j]=t.charAt(j);
                if (G[i][j]=='G') D[i][j]='R';
                else D[i][j]=G[i][j];
            }
        }
        int aa =Ans(G);
        
        vis = new boolean[N][N];
        System.out.println(aa+" "+Ans(D));
    }
 
}
 

이게 일단 첫번째 시도이다. 일단 구역의 개수를 세는 것이기에 BFS를 이용해보았다. 그러나 메모리 초과....

 

두번째 시도 (성공.....)

아...뭐 맞기야 했다...근데 메모리 225968kb에 552ms ......... 심지어 메모리 초과를 피하기 위해 que의 첫번째 인덱스의 값을 줄이기만 했다.......더 나은 코드가 있지 않을까싶으니 좀 더 고쳐보자...

import java.io.InputStreamReader;
import java.io.BufferedReader;
 
 
public class B_10026 {
    static boolean[][] vis;
    static int N;
    static char[][] G;
    static boolean check(int a , int b) {
        if  (a>=N||a<0) return false;
        if (b>=N||b<0) return false;
        return true;
    }
    
    static void bfs(int a,int b) {
        char k = G[a][b];
        int[][] que = new int[10000][2];
        int[][] dic = {{1,0},{0,1},{-1,0},{0,-1}};
        int front=0,rear=0;
        que[rear][0]=a;que[rear++][1]=b;
        vis[a][b] = true;
        while(front!=rear) {
            int x=que[front][0],y=que[front++][1];
            for (int i=0;i<4;i++) {
                int nx=x+dic[i][0],ny=y+dic[i][1];
                if (check(nx,ny)==true) {
                    if (G[nx][ny]!=k) continue;
                    if (vis[nx][ny]==true) continue;
                    que[rear][0]=nx;que[rear++][1]=ny;
                    vis[nx][ny]=true;
                }
            }
        }
    }
    static int Ans() {
        int h=0;
        for (int i=0;i<N;i++) 
            for (int j=0;j<N;j++) 
                if (vis[i][j]!=true) { 
                    bfs(i,j); h+=1;
                }
 
        return h;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        G = new char[N][N];
        vis = new boolean[N][N];
        for (int i=0;i<N;i++) {
            String t = br.readLine();
            for (int j=0;j<N;j++) {
                G[i][j]=t.charAt(j);
            }
        }
        int aa =Ans();
        for (int i=0;i<N;i++)
            for(int j=0;j<N;j++) {
                if (G[i][j]=='G') G[i][j]='R';
            }
        vis = new boolean[N][N];
        System.out.println(aa+" "+Ans());
    }
 
}
 

아직도 줄일 방법을 잘 모르겠다... 내일 다시 해봐야될듯....