백준 2178번 ☆

문제

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

2178번: 미로 탐색

import java.util.Scanner;

public class Main2178 {
	
	static int N,M;
	static int[][] maze;
	static boolean[][] visited;
	static int[] axisX = {1,-1,0,0};
	static int[] axisY = {0,0,1,-1};
	static int min = Integer.MAX_VALUE;
	
	public static void dfs(int count, int x, int y) {

		visited[x][y] = true;
		
		if (x == N-1 && y == M-1) {
			min = Math.min(min, count);
		}
		
		for (int i=0; i<4; i++) {
			int nx = x + axisX[i];
			int ny = y + axisY[i];

			if (nx>=0 && ny>=0 && nx<N && ny<M) {
				if (maze[nx][ny] == 1 && !visited[nx][ny]) {
					dfs(count+1, nx, ny);
				}
			}
		}
		
		visited[x][y] = false;
	}
 
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		maze = new int[N][M];
		visited = new boolean[N][M];
		
		for (int i=0; i<N; i++) {
			String temp = sc.next();
			for (int j=0; j<M; j++) {
				maze[i][j] = temp.charAt(j)-'0';
			}
		}
		
		sc.close();
		
		dfs(1, 0, 0);
	
		System.out.println(min);
	}
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main2178_1 {
	
	static int N,M;
	static int[][] maze;
	static boolean[][] visited;
	static int[] axisX = {1,-1,0,0};
	static int[] axisY = {0,0,1,-1};
	
	public static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {x,y});
		
		while(!q.isEmpty()) {
			int[] now = q.poll();
			int noX = now[0];
			int noY = now[1];
			
			for (int i=0; i<4; i++) {
				int neX = noX + axisX[i];
				int neY = noY + axisY[i];
				
				if (neX<0 || neY<0 || neX>=N || neY>=M) {
					continue;
				} 
				if (visited[neX][neY] || maze[neX][neY] == 0) {
					continue;
				} 
				
				q.add(new int[] {neX, neY});
				maze[neX][neY] = maze[noX][noY] + 1;
				visited[neX][neY] = true;
				
			}
		}
		
	}
 
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		maze = new int[N][M];
		visited = new boolean[N][M];
		
		for (int i=0; i<N; i++) {
			String temp = sc.next();
			for (int j=0; j<M; j++) {
				maze[i][j] = temp.charAt(j)-'0';
			}
		}
		
		sc.close();
		
		visited[0][0] = true;
		bfs(0, 0);
	
		System.out.println(maze[N-1][M-1]);
	}
}

1. dfs 문제로 분류가 되어있어 dfs로 접근했으나.. 시간초과 + bfs문제라는 사실을 알게됐다.

 

2. 첫번째 코드는 dfs 두번재는 bfs 둘다 올바른 출력이긴하다. 다만 시간초과라는 조건에서 정답유무가 갈린다.

 

3. 이번문제를 통해 bfs로 푸는 방식을 알게됐다. 개념은 이전에도 cs공부를 하며 익힌바가 있지만 실제 적용하는 것은 이번이 처음이다. 원리 자체는 어렵지 않다. 다만 queue를 내가 자체적으로 구현하려면 아직은 무리인듯 싶다.

 

 

참고 및 출처 : https://wiselog.tistory.com/163

[백준 2178] 미로 탐색(Java)