[SWEA] #1226 - 미로1

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD 

SW Expert Academy

 

💡 문제

---

[설명]

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

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

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

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

 

[제약 사항]

1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

 

💡 아이디어

---

4방 탐색 + 백트래킹을 이용하면 이 문제를 해결할 수 있다.

현재 지점에서 상, 하, 좌, 우 네 방향을 탐색해 갈 수 있는 길이 있다면 Stack에 넣고 Stack에서 하나 꺼내 그 위치로 이동한다.

갈 수 있는 길이 없다면 Stack에서 하나를 꺼내 그 위치로 이동한다.

이 과정에서 이미 갔던 곳은 표시를 해놔야 재방문을 피할 수 있다.

과정을 반복하다가 도착점에 도착하면 길이 있다고 판단할 수 있다.

 

💡 소스코드

---

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Stack;

public class P_1226 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		for (int TC = 1; TC <= 10; TC++) {
			int T = Integer.parseInt(br.readLine());

			int[][] maze = new int[16][16];

			for (int i = 0; i < 16; i++) {//2차원 배열에 미로 저장
				String s = br.readLine();
				for (int j = 0; j < 16; j++) {
					maze[i][j] = s.charAt(j) - '0';
				}
			}

			System.out.println("#" + TC + " " + solve(maze));//solve() 호출
		}

		br.close();
	}

	public static int solve(int[][] maze) {
		Stack<Integer> X = new Stack<>();//X값을 저장하는 stack
		Stack<Integer> Y = new Stack<>();//Y값을 저장하는 stack
		int[] dx = { -1, 0, 1, 0 };//상, 우, 하, 좌에 따라 변하는 X값
		int[] dy = { 0, 1, 0, -1 };//상, 우, 하, 좌에 따라 변하는 Y값
		boolean[][] visited = new boolean[maze.length - 1][maze.length - 1];//방문한 곳을 나타내는 2차원 배열
		int flag = 0;

		X.push(1);//시작 X값
		Y.push(1);//시작 Y값

		while (true) {
			//현재 X, Y값을 Stack에서 pop
			int curX = X.pop();
			int curY = Y.pop();

			visited[curX][curY] = true;//현재 X, Y는 방문했다는 표시

			for (int k = 0; k < 4; k++) {//상, 하, 좌, 우를 살펴볼 거임
				//만약 살펴보다 도착지가 있으면 무한 loop 탈출
				if (maze[curX + dx[k]][curY + dy[k]] == 3) {
					flag = 1;
					break;
				}
				
				//도착지가 아니면 현재 위치에서 갈 수 있는 곳을 Stack에 push
				else if (maze[curX + dx[k]][curY + dy[k]] == 0 && visited[curX + dx[k]][curY + dy[k]] == false) {
					X.push(curX + dx[k]);
					Y.push(curY + dy[k]);
				}
			}

			if (flag == 1)//만약 flag = 1이면 도착지가 있다는 의미
				break;

			else if (X.isEmpty() && Y.isEmpty())//flag = 0이면서 stack이 비었으면 모든 길을 탐색했지만, 도착지를 찾지 못했다는 의미
				break;
		}

		return flag;
	}
}

 

💡 결과

---