[백준] 16946 벽 부수고 이동하기 4 - BFS + 방문처리 + 시간초과 JAVA

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

16946번: 벽 부수고 이동하기 4

코드설명

BFS 문제입니다.

 

문제에서 중복되는 연산은 모두 제거하고, 최대한 효율적으로 코딩하여야 통과할 수 있습니다.

1. StringBuilder 활용하여 출력 시간 감소

2. simulate(Node start), BFS 함수에서 Indexing 하는 과정에서 visited 대신에 Indexing으로 사용하여 쓸모없는 메모리 사용안하기

3. 해당 벽이 0일떄만, 그리고 아직 Indexing 안된경우에만 BFS를 실행합니다.

for(int i=0;i<N;i++) {
    for(int j=0;j<M;j++) {
        if(map[i][j] == '0' && Indexing[i][j] == 0) { //이동할 수 있는 벽일경우에만.
            simulate(new Node(i,j));
        }
    }
}

 

최대한 효율적으로 짜야 시간초과에서 통과합니다.

 

코드

최적화 진행코드, 특히 visited[][] 사용대신 이미 기존에 사용하던 Indexing[][] 이 아직 안된 부분은 방문하지 않은곳이므로 해당 지역을 먼저 체크하는 과정을 진행했고, StringBuilder를 활용하여 진행하면 시간초과를 벗어날 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int N, M;
	public static char[][] map;
	public static int[] dx= {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int[][] Indexing;
	public static int[][] moveable;
	public static int indexNumber=1;
	public static int[][] answer;
	public static HashSet<Integer> hashset = new HashSet<Integer>();
	public static StringBuilder sb = new StringBuilder();
    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 char[N][M];
    	answer = new int[N][M];
    	Indexing = new int[N][M];
    	moveable = new int[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] == '0' && Indexing[i][j] == 0) { //이동할 수 있는 벽일경우에만.
    				simulate(new Node(i,j));
    			}
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] == '1') { //이동할 수 있는 벽일경우에만.
    				hashset.clear();
    				int countCnt = 1;
    				for(int dir=0;dir<4;dir++) {
    					int ni = i + dx[dir];
    					int nj = j + dy[dir];
    					if(ni < 0 || ni >= N || nj < 0 || nj >= M) continue;
    					if(Indexing[ni][nj] == 0) continue;
    					if(!hashset.contains(Indexing[ni][nj])) {
    						hashset.add(Indexing[ni][nj]);
    						countCnt += moveable[ni][nj];
    					}    						
    				}
    				answer[i][j] = countCnt;
    				sb.append( (answer[i][j]) % 10);
    			}
    			else{
    				sb.append(0);
    			}
    		}
    		sb.append("\n");
    	}
    	
    	System.out.println(sb.toString());
    }
    
    public static void simulate(Node start) {
    	Queue<Node> q = new LinkedList<>();
    	Queue<Node> storeQ = new LinkedList<>();
    	q.offer(start);
    	storeQ.offer(start);
    	Indexing[start.r][start.c]=indexNumber; 
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		for(int dir=0;dir<4;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			if(nr < 0 || nr >= N || nc < 0 || nc >= M ) continue;
    			if(Indexing[nr][nc] > 0) continue;
    			if(map[nr][nc] == '0') { //이동할 수 있는 경우에만.
    				Indexing[nr][nc] = indexNumber;
    				q.offer(new Node(nr, nc));
    				storeQ.offer(new Node(nr, nc));
    			}
    		}
    	}
    	
    	int maxCnt = storeQ.size();
    	while(!storeQ.isEmpty()) {
    		Node temp = storeQ.poll();
    		int r = temp.r;
    		int c = temp.c;
    		moveable[r][c] = maxCnt;
    	}
    	indexNumber += 1;
    }
    
}

class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r=r;
		this.c=c;
	}
}

 

처음에 시간초과 난 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int N, M, K;
	public static char[][] map;
	public static boolean[][] visited;
	public static int[] dx= {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
//	public static int answer = 0;
	public static int[][] answer;
	
    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 char[N][M];
    	answer = new int[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] == '1') { //벽일경우에만.
    				simulate(new Node(i,j, 1));
    			}
    		}
    	}
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			System.out.print(answer[i][j]);
    		}
    		System.out.println();
    	}
    	
    }
    
    public static void simulate(Node start) {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(start);
    	visited = new boolean[N][M];
    	visited[start.r][start.c] = true;
    	int maxCnt = 0;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		int moveCnt = temp.moveCnt;
    		maxCnt += 1;
    		for(int dir=0;dir<4;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			if(nr < 0 || nr >= N || nc < 0 || nc >= M ) continue;
    			if(visited[nr][nc] == true) continue;
    			if(map[nr][nc] == '0') {
    				visited[nr][nc] =true;
    				q.offer(new Node(nr, nc, moveCnt + 1));
    			}
    		}
    	}
    	answer[start.r][start.c]= maxCnt; 
    	
    }
    
}

class Node{
	int r;
	int c;
	int moveCnt;
	public Node(int r, int c, int moveCnt) {
		this.r=r;
		this.c=c;
		this.moveCnt = moveCnt;
	}
}