[SWEA] 1227. [S/W 문제해결 기본] 7일차 - 미로2

문제

아래 그림과 같은 미로가 있다. 100*100 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.

가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.

주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.

아래의 예시에서는 도달 가능하다.

아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다.
 

 

위의 예시는 공간상의 이유로 100x100이 아닌 16x16으로 주어졌음에 유의한다.

 

풀이방법

DFS(깊이 우선 탐색)을 이용해 문제 해결.

 

2의 값이 저장된 노드를 중심으로 상, 하, 좌, 우 갈 수 있는 노드를 탐색하며 모든 경로를 찾는다.

 

모든 경로를 찾았을 때, 3이 저장된 노드를 방문하는 경로를 찾지 못했다면 0을 출력, 찾았다면 1을 출력한다.

 

소스코드

package samsung;

import java.util.*;

public class s_1227 {
	static int[][] map;
	static int[][] v;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int find;
	
	public static void dfs(int x, int y) {
		if(find == 1)
			return;
		if(map[x][y] == 3) {
			find = 1;
			return;
		}
		v[x][y] = 1;
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 0 && ny >= 0 && nx < 100 && ny < 100) {
				if(v[nx][ny] == 0 && map[nx][ny] != 1) {
					dfs(nx,ny);
				}
			}
		}
		v[x][y] = 0;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for(int t = 1; t <= 10; t++) {
			int tc = sc.nextInt();
			map = new int[100][100];
			v = new int[100][100];
			int x = 0;
			int y = 0;
			find = 0;
			
			for(int i = 0; i < 100; i++) {
				String s = sc.next();
				for(int j = 0; j < 100; j++) {
					map[i][j] = s.charAt(j) - '0';
					if(map[i][j] == 2) {
						x = i;
						y = j;
					}
				}
			}
			dfs(x, y);
			System.out.println("#" + t + " " + find);
		}
	}
}