백준 : 17090 미로 탈출하기

visit의 방문을 체크하면서  list에 담고 범위를 벗어낫을 경우 ans++ 더하면된다.

 

이때 다음 방문하는 곳에 탈출한적이잇다면 바로 탈출 할수있게 ret 배열을 초기화해준다.

 

package 삼성;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

import 삼성.미로탈출하기.Pair;

public class 미로탈출하기 {
	static int U[] = { -1, 0 };
	static int R[] = { 0, 1 };
	static int L[] = { 0, -1 };
	static int D[] = { 1, 0 };
	static int N, M;

	static class Pair {
		int y;
		int x;

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}
	}

	static char map[][];
	static boolean visit[][];
	static boolean ret[][];
	static int ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new char[N][M];
		visit = new boolean[N][M];
		ret = new boolean[N][M];

		for (int i = 0; i < N; i++)
			map[i] = br.readLine().toCharArray();

		ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visit[i][j]) {
					BFS(i, j);
				}
			}
		}

		System.out.println(ans);

	}

	static Queue<Pair> q;
	static ArrayList<Pair> list;

	private static void BFS(int y, int x) {

		list = new ArrayList<>();
		q = new LinkedList<>();
		q.add(new Pair(y, x));
		visit[y][x] = true;

		while (!q.isEmpty()) {
			Pair cur = q.poll();
			list.add(cur);

			// check 한곳이 아니면 visit을 해본다.
			int ny = 0;
			int nx = 0;

			if (map[cur.y][cur.x] == 'U') {
				ny = cur.y + U[0];
				nx = cur.x + U[1];
			} else if (map[cur.y][cur.x] == 'R') {
				ny = cur.y + R[0];
				nx = cur.x + R[1];
			} else if (map[cur.y][cur.x] == 'L') {
				ny = cur.y + L[0];
				nx = cur.x + L[1];
			} else if (map[cur.y][cur.x] == 'D') {
				ny = cur.y + D[0];
				nx = cur.x + D[1];
			}
//			System.out.println(ny+" "+nx);
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) {
				// 실패 방문한 부분 check true 하고 ret false
				for (Pair p : list) {
					ret[p.y][p.x] = true;
					ans++;
				}
				return;
			}
			if (ret[ny][nx]) {
				for (Pair p : list) {
					ret[p.y][p.x] = true;
					ans++;
				}
				return;
			}

			if (visit[ny][nx])
				continue;
			visit[ny][nx] = true;
			q.add(new Pair(ny, nx));
		}
	}
}