[SWEA] 1226. 미로1 (JAVA)

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

SW Expert Academy

[문제]

아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.
가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.
주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.
아래의 예시에서는 도달 가능하다.

[풀이]

1. String 형태로 들어온 입력을 int형 이차원 배열에 저장하여 map을 만들었다.

2. 방문 확인을 위한 visited 이차원 배열을 만들었다.

3. map에서 2를 만나면 시작점

4. 시작점 위치를 queue에 넣는다.

5. 이 때 queue는 int배열형 queue를 생성하였다.

6. map에서 3을 만나면 종료지점, answerX와 answerY에 x,y 좌표값을 저장해두었다.

7. queue가 빌 때까지 탐색을 한다.

8. queue에서 꺼내진 좌표를 기준으로 상, 하, 좌, 우를 탐색한다. (미로이기 때문에 네 방향으로 이동이 가능하다)

9. 배열 크기를 벗어나면 안되므로 예외처리를 해준다.

10. 상하좌우를 탐색하면서 길이고(좌표값이 0이고), 방문하지 않은 곳이라면 queue에 넣고 방문 처리를 해준다.

11. 도착지점, 즉 좌표값이 3인 경우도 방문 처리를 하고 큐에 좌표값을 넣어준다.

12. 모든 탐색이 끝난 후 visited 배열에서 좌표 answerX, answerY 값이 1이라면 도착지점까지 방문이 된 것이다.

package A0207;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SWEA_미로1 {
	
	static int[][] map;
	static int[][] visited;
	static int answerX, answerY;
	
	static int[][] search(int[][] map) {
	
		Queue<int[]> queue = new LinkedList<int[]>();
		
		int[] dx = {0,0,-1,1};
		int[] dy = {-1,1,0,0};
		
		for(int i=0;i<16;i++) {
			for(int j=0;j<16;j++) {
				if(map[i][j]==2) { //2이면 시작지점
					queue.offer(new int[] {i,j}); //큐에 x,y 좌표 넣는다
				}
				else if(map[i][j]==3) { //3이면 도착지점
					answerX=i; //정답 x,y 값에 좌표 넣는다
					answerY=j;
					break;
				}
			}
		}
		
		while(!queue.isEmpty()) {
			int[] tmp = queue.poll();
			int x = tmp[0];
			int y = tmp[1];
			//queue에서 나온 점을 기준, 상하좌우 본다
			for(int i=0;i<4;i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx<0||nx>15||ny<0||ny>15) continue;
				if(map[nx][ny]==0&&visited[nx][ny]==0) { //길이고 방문 안했으면
					visited[nx][ny]=1; //방문처리
					queue.offer(new int[] {nx, ny}); //큐에 넣는다
				}
				else if(map[nx][ny]==3) { //3인 경우도 방문처리(도착점)
					visited[nx][ny]=1;
					queue.offer(new int[] {nx, ny});
				}
			}
		}
		
		return visited;
		
	}
	public static void main(String[] args) throws Exception {
		
		System.setIn(new FileInputStream("input_maze.txt")); 
		Scanner sc = new Scanner(System.in);
		int T;
		T=10;
		
		for(int test_case=1;test_case<=T;test_case++) {
			map=new int[16][16];
			visited=new int[16][16];
			answerX=0;
			answerY=0;
			int n = sc.nextInt(); //테스트케이스 번호
			for(int i=0;i<16;i++) {
				char[] tmp = sc.next().toCharArray();
				for(int j=0;j<16;j++) {
					map[i][j]=tmp[j]-'0'; //'0'을 빼줘서 char -> int 형변환
				}
			}
			
			search(map);
			if(visited[answerX][answerY]==1) System.out.println("#"+test_case+" "+1);
			else System.out.println("#"+test_case+" "+0);
			
		}
	}
	

}

[소감]

길찾기 문제는 너무 많이 나오는 문제인 것 같다. 많이 풀다보면 익숙해지겠지..? 놓치는 부분이 너무 많은 것 같다.