[문제] SWEA 1227번 미로2

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14wL9KAGkCFAYD&categoryId=AV14wL9KAGkCFAYD&categoryType=CODE&problemTitle=1227&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

내 풀이

 

dfs

public class Solution {
	static int start[], end[], N;
	static int[][] map;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int ans;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = 10;
		N = 100;
		for (int tc = 1; tc <= T; tc++) {
			in.readLine();
			map = new int[N][N];
			start = new int[2];
			end = new int[2];
			for (int i = 0; i < N; i++) {
				String s = in.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = s.charAt(j) - '0';
					if (map[i][j] == 2) {
						start[0] = i;
						start[1] = j;
					}
					if (map[i][j] == 3) {
						end[0] = i;
						end[1] = j;
					}
				}
			}
			ans = 0;
			 dfs(start[0], start[1]);
			sb.append("#").append(tc).append(' ').append(ans).append('\n');
		}
		System.out.println(sb);
	}

	static void dfs(int x, int y) {
		if (x == end[0] && y == end[1]) {
			ans = 1;
			return;
		}
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 0 || map[nx][ny]==3) {
				map[nx][ny] = -1;
				dfs(nx, ny);
			}
		}
	}
}