[백준] 16932 모양 만들기 - BFS or DFS + 아이디어 JAVA

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

16932번: 모양 만들기

문제풀이

처음에는 일반적인 BFS문제인줄 알았습니다.

문제 조건에 

• 2 ≤ N, M ≤ 1,000

를 보면 1000 x 1000 x 1000 x 1000 = 1,000,000,000,000 ( 1조의 계산결과?? ) 

(가로x세로)x(BFS들어갔을때 연산으로 최대 1000번 x 1000) 의 최악의 결과가 있습니다. 

 

 

시간초과를 위해서는

각 Group을 Indexing 시켜서 진행합니다. 즉, Grouping 시킵니다.

시간초과를 해결하기 위하여 예시입력입니다.

3 3
0 1 1
0 0 1
0 1 0

Grouping을 통하여 index를 매겨주면 아래의 그림처럼 Map을 변경시켜줍니다.

0 2 2
0 0 2
0 3 0

이렇게 됩니다.

 

indexKey를 2부터 시작하는 이유는 Map이 1인경우와 구분하여 Visited 처리를 동시에 진행하기 위하여입니다.

현재로써는 이해가 안되시겠지만, 코드를 보면 이해가 되실 것 입니다.

 

또한 에러가 있어서 시간을 잡아먹힌 부분은, 

아래의 getByIndex에서  HashMap을 활용하여 진행할떄 HashMap에 값이 없으면 NULL이 나옵니다.

그러므로 map[nx][ny] = 0 일경우 continue 조건을 넣음으로써 반드시 Grouping한 값을 Key로써 넣어주어야 sizeTemp에  Size를 더하는 코드에서 NULLPOINTERException 에러가 나지 않습니다.

public static void getByIndex(int startx, int starty) {
    HashSet<Integer> visitedHashSet = new HashSet<>();
    for(int dir=0;dir<4;dir++) {
        int nx = startx + dx[dir];
        int ny = starty + dy[dir];
        if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
        if(map[nx][ny] == 0) continue;
        if(visitedHashSet.contains(map[nx][ny])) continue;
        //방문처리
        visitedHashSet.add(map[nx][ny]);
        //해당 index의 Size값을 더함
        sizetemp += indexHasmmap.get(map[nx][ny]);
    }
}

 

 

코드

처음에 시간초과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N,M;
	public static int[][] map;
	public static Queue<Node> q = new LinkedList<>();
	public static boolean[][] visited;
	public static int result = 0;
	public static int realresult = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	map = new int[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<M;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			visited = new boolean[N][M];
    			if(map[i][j] == 0) {
    				
    				//1로 변경
    				map[i][j] = 1;
    				result = 1;
    				Simulate(i, j);
    				realresult = Math.max(realresult, result);
    				map[i][j] = 0;
    				//다시 0으로 초기화
    			}
    		}
    	}
    	System.out.println(realresult);
    	
    }
    
    public static void Simulate(int startx, int starty) {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	
    	q.offer(new Node(startx, starty, 1));
    	visited[startx][starty] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x= temp.x;
    		int y = temp.y;
    		int cnt = temp.cnt;
    		
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
    			if(visited[nx][ny] == true || map[nx][ny] == 0) continue;
    			q.offer(new Node(nx, ny, cnt + 1));
    			visited[nx][ny] = true;
    			result+=1;
    		}
    		
    	}
    	
    }
    
    
    
}
 
class Node{
	int x;
	int y;
	int cnt;
	public Node(int x, int y, int cnt) {
		this.x=x;
		this.y=y;
		this.cnt = cnt;
	}
}

 

 

각 그룹을 Grouping 하여 해결한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N,M;
	public static int[][] map;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static HashMap<Integer, Integer> indexHasmmap = new HashMap<>();
	public static ArrayList<Node> zeroArr = new ArrayList<>();
	public static int indexKey=2;
	public static int sizetemp = 0;
	public static int result = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	map = new int[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<M;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    			if(map[i][j] == 0) zeroArr.add(new Node(i,j));
    		}
    	}
    	
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] == 1) {
    				makeIndex(i, j);  				
    			}
    		}
    	}
    	
    	for(int i=0;i<zeroArr.size();i++) {
    		sizetemp = 1;
    		getByIndex(zeroArr.get(i).x, zeroArr.get(i).y);
    		result = Math.max(result, sizetemp);
    	}
    	
    	System.out.println(result);
    	
    	
    }
    
    public static void getByIndex(int startx, int starty) {
    	HashSet<Integer> visitedHashSet = new HashSet<>();
    	for(int dir=0;dir<4;dir++) {
    		int nx = startx + dx[dir];
    		int ny = starty + dy[dir];
    		if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
    		if(map[nx][ny] == 0) continue;
    		if(visitedHashSet.contains(map[nx][ny])) continue;
    		//방문처리
    		visitedHashSet.add(map[nx][ny]);
    		//해당 index의 Size값을 더함
    		sizetemp += indexHasmmap.get(map[nx][ny]);
    	}
    }
    
    public static void makeIndex(int startx, int starty) {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(startx, starty));
    	map[startx][starty] = indexKey;
    	int indexSize = 1;
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			
    			if(nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
    			if(map[nx][ny] != 1) continue;
    			
    			q.offer(new Node(nx, ny));
    			map[nx][ny] = indexKey;
    			indexSize += 1;
    		}
    	}
    	indexHasmmap.put(indexKey, indexSize);
    	indexKey+=1;
    }
    
    
}
 
class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x=x;
		this.y=y;
	}
 
}