[JAVA] SWEA 1226번 미로1

문제

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

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

 

(1, 1)이고 도착점은 (13, 13)이다.

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

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

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

입력

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).

풀이

미로의 0 값을 좌표 형태로 저장하였다.

 

입력을 2차원 배열의 각 좌표에 넣어주고,

 

큐를 Queue<Point>로 선언해 x, y 좌표를 저장할 수 있도록 하였다.

 

상하좌우 4방향으로 움직이며 길을 찾기 위해 dx, dy 배열을 사용하였으며, 

 

루프를 돌며 newX, newY로 갈 길을 정하고 움직이며 방문한 자리의 값을 true로 바꿔주었다.

 

3을 만나면 1을 반환하도록 하였다.

 

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class 미로1 {
	public static int [][] maze;
	public static boolean [][] visited;
	public static Queue<Point> q;
	
	public static int isWay() {
		q = new LinkedList<>();
		visited = new boolean[16][16];
		
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		
		int startX = 1;
		int startY = 1;
		Point v;
		
		q.add(new Point(startY, startX));
		visited[startY][startX] = true;
		
		while (!q.isEmpty()) {
			v = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int newX = v.x + dx[i];
				int newY = v.y + dy[i];
				
				if (newX < 0 || newX >= maze.length || newY < 0 || newY >= maze.length)
					continue;
				
				if (maze[newY][newX] == 0 && !visited[newY][newX]) {
					q.add(new Point(newY, newX));
					visited[newY][newX] = true;
				}
				else if (maze[newY][newX] == 3)
					return 1;
			}
		}
		return 0;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for (int test_case = 1; test_case <= 10; test_case++) {
			maze = new int[16][16];
			br.readLine();
			
			for (int i = 0; i < maze.length; i++) {
				String str = br.readLine();
				for (int j = 0; j < maze.length; j++) {
					maze[i][j] = str.charAt(j) - '0';
				}
			}

			System.out.println("#" + test_case + " " + isWay());
		}
	}
}