[JAVA]백준 2178번: 미로 탐색

 

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

2178번: 미로 탐색

 

 

 

| 문제 해결방법

 

관련 알고리즘 : bfs (dfs로 시간초과가 난 후 방법을 bfs로 변경)

 

 

< bfs , dfs의 시간복잡도 >

인접행렬

* O(V^2)

 

인접리스트 

* O(V+E) 

 

 

처음에 인접행렬 + dfs로 풀 방법은 시간초과

 

이후 인접리스트 + bfs로 방법을 바꾸어 풀어서 해결했다.

 

[JAVA] 해설 코드

1. 인접행렬 + dfs (시간초과)

package graph;

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 BOJ_2178 {
	
	static int R, C, result,count;
	static int[][] arr;
	static boolean[][] visited;
	static int[][] dir = {{1,0},{0,1},{0,-1},{-1,0}};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		arr = new int[R][C];
		visited = new boolean[R][C];
		result = Integer.MAX_VALUE;
		for(int i=0;i<R;i++) {
			 char[]  cArr=br.readLine().toCharArray();
			for(int j=0;j<C;j++) {
				arr[i][j] = cArr[j] -'0';
			}
		}	
		visited[0][0] = true;
		find(0,0,1);
		
		System.out.println(result);

	}

	private static void find(int r, int c, int count) {
		
		
		// 기저 arr[R-1][C-1] 에 도착했을 경우
		if(r == R-1 && c ==C-1) {
			
			result = Math.min(result,count);
			return;
		}
		
        // (사방 탐색)갈 수 있을 길 탐색 후 재귀
		for(int i=0;i<4;i++) {
			int nr  = r + dir[i][0];
			int nc = c + dir[i][1];
			
            // 방문했거나 범위를 벗어나면 continue
			if(!isIn(nr,nc) || visited[nr][nc]) continue;
			
			if(arr[nr][nc]==1) {
            
				visited[nr][nc] = true;
				
				find(nr,nc,count+1);
				
				visited[nr][nc] = false;
			}
			
		}
		return;
		
	}
	
	private static boolean isIn(int r, int c) {
		return r>=0 && r<R && c>=0 && c<C;
	}

	
}

 

 

2. 인접리스트 + bfs (성공)

 

package graph;

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 BOJ_2178_bfs {
	
	static int R, C, result,count;
	static int[][] arr;
	static boolean[][] visited;
	static int[][] dir = {{1,0},{0,1},{0,-1},{-1,0}};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		arr = new int[R][C];
		visited = new boolean[R][C];
		result = Integer.MAX_VALUE;
		for(int i=0;i<R;i++) {
			 char[]  cArr=br.readLine().toCharArray();
			for(int j=0;j<C;j++) {
				arr[i][j] = cArr[j] -'0';
			}
		}	
		visited[0][0] = true;
		find(0,0);
		
		System.out.println(arr[R-1][C-1]);

	}

	private static void find(int r, int c) {
		
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {r,c});
        
		while(!q.isEmpty()) {
			int[] d = q.poll();
			int nr = d[0];
			int nc = d[1];
			for(int i=0;i<4;i++) {
				int nextX = nr + dir[i][0];
				int nextY = nc + dir[i][1];
				
                // 범위를 벗어나거나, 방문했던 지점이거나, 갈 수 있는 길(1)이 아닌 경우 continue;
				if(!isIn(nextX,nextY) || visited[nextX][nextY] || arr[nextX][nextY]==0) continue;
				
				q.add(new int[] {nextX,nextY});
				visited[nextX][nextY] = true;
				arr[nextX][nextY] = arr[nr][nc]+1;
			}
			
		}
		
	}
	
	private static boolean isIn(int r, int c) {
		return r>=0 && r<R && c>=0 && c<C;
	}
	
	
	
}

 

[제출] 메모리 및 시간

위 : 인접리스트 + bfs (성공)

아래 : 인접행렬 + dfs (시간초과)