[SWEA] JAVA - 1227. 미로2

생각

(1,1) 에서 시작하여 (13,13)까지 도달할 수 있는지를 판단하는 문제입니다.

DFS를 사용하여 도착지점까지 갈 수 있는지를 찾아줬습니다.

 

1. 출발좌표에서 DFS 탐색을 시작합니다.

2. dy,dx 방향 벡터를 이용하여 사방탐색을 합니다.

3. 다음좌표를 방문하지 않았고 벽이 아니라면 다음 좌표를 파라미터에 넣고 다음 단계를 정하러 한단계 더 들어갑니다.

4. 더 이상 이동할 수 없으면 이전에 다녀온 방문표시를 모두 해제합니다.

5. 기저조건인 도착지점에 도착한다면 ans=1 로 업데이트 시켜줍니다.

Java code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SWEA_1227_미로2 {
	static int[][] map;
	static boolean[][] visited;
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = 10;
		
		for (int i = 1; i <= TC; i++) {
			int t = Integer.parseInt(br.readLine());
			map = new int[100][100];
			visited = new boolean[100][100];
			//입력
			for (int y = 0; y < 100; y++) {
				String s = br.readLine();
				for (int x = 0; x < 100; x++) {
					int val = s.charAt(x)-'0';
					map[y][x] = val;
				}
			}
			ans = 0;
			//solve
			solve(1,1);
			
			sb.append("#").append(t).append(" ").append(ans).append("\n");
			
		}// end of test case
		System.out.print(sb);
		
	}// end of main
	
	private static void solve(int i, int j) {
		if(map[i][j] == 3) {
			ans = 1;
			return;
		}
		visited[i][j] = true;
		for (int k = 0; k < 4; k++) {
			int ny = i + dy[k];
			int nx = j + dx[k];
			if(ny >= 100 || ny < 0 || nx >= 100 || nx < 0) continue;
			if(map[ny][nx] != 1 && !visited[ny][nx]) {
				visited[ny][nx] = true;
				solve(ny,nx);
				visited[ny][nx] = false;
			}
		}

	}

}