[SWEA] [자바] 1953. 탈주범 검거

문제 출처
swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

SW Expert Academy

---

1. 풀이 접근

  ㆍ 파이프 리스트 정리
     ※ 상 : 0 , 하 : 1 , 좌 : 2 , 우 : 3
     - 1번은 상하좌우 : "0123"
     - 2번은 상하 : "01"
     - 3번은 좌우 : "23"
     - 4번은 상우 : "03"
     - 5번은 하우 : "13"
     - 6번은 하좌 : "12"
     - 7번은 상좌 : "02"

  ㆍ 현재 탈주범의 위치를 시작으로 BFS탐색 시작
     ※ BFS 탐색 시 소요 시간을 기준으로 L까지 잘라서 하거나, Queue에 넣을 클래스에 소요시간을 저장해두고 찾는 방법 등 가능. 필자는 전자 사용.
     - list에 지도의 파이프 구성을 삽입하면 파이프 형태가 나오게 설계
       * ex.) map[1][1] = 1 ==> list[map[1][1] ==> list[1] = "0123" : 상하좌우 다 갈 수 있음
     - list의 char를 추출해서 상하좌우로 이동할 수 있게 설계
     - 이동가능하면 다음 큐에 저장, 방문배열에 체크

  ㆍ 방문배열에 방문한 갯수 체크 및 출력

---

2. 소스코드

github.com/Choi-JinYeong/Solve_Alg/tree/master/Solve_Algs_SWEA/src/SWEA_1953

Choi-JinYeong/Solve_Alg

package SWEA_1953;
import java.util.ArrayList;
import java.util.Scanner;

class po {
	int x;
	int y;

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

public class Solution {

	public static int T, N, M;
	public static int[][] map, po, isVisit;
	public static int sn, sm, L;
	public static po Queue[];
	public static int front, rear;

	// 상 하 좌 우
	public static int[] mx = { 0, 0, -1, 1 };
	public static int[] my = { -1, 1, 0, 0 };
	public static ArrayList<ArrayList<Integer>> list;
	public static String[] lists;

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);

		T = Integer.parseInt(sc.nextLine());

		for (int i = 0; i <= 7; i++) {
			list = new <Integer>ArrayList();
		}

		lists = new String[8];
		lists[1] = "0123";
		lists[2] = "01";
		lists[3] = "23";
		lists[4] = "03";
		lists[5] = "13";
		lists[6] = "12";
		lists[7] = "02";

		for (int test = 1; test <= T; test++) {

			String[] input = sc.nextLine().split(" ");
			N = Integer.parseInt(input[0]);
			M = Integer.parseInt(input[1]);

			Queue = new po[N * M * 4];
			front = 0;

			map = new int[N][M];
			po = new int[N][M];
			isVisit = new int[N][M];
			sn = Integer.parseInt(input[2]);
			sm = Integer.parseInt(input[3]);
			L = Integer.parseInt(input[4]);

			Queue[rear++] = new po(sm, sn);

			for (int i = 0; i < N; i++) {
				String[] input1 = sc.nextLine().split(" ");
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(input1[j]);
				}
			}

			solve();

			int a = check();
			System.out.println("#" + test + " " + a);
			front = 0;
			rear = 0;
		}
	}

	public static void solve() {

		for (int i = 0; i < L; i++) {
			// 파이프 -> 이동할 수 있는 곳 계산

			int s = front;
			int e = rear;
			//System.out.println((i + 1) + " : " + s + " / " + e);
			for (int j = s; j < e; j++) {
				if (i == 0) {

					isVisit[sn][sm] = 1;
				} else {
					int x = Queue[front].x;
					int y = Queue[front].y;
					front++;

					if (map[y][x] != 0) {
						String pipe = lists[map[y][x]];
						int pleng = pipe.length();
						int pidx = 0;
						for (int k = 0; k < pleng; k++) {
							int m = Integer.parseInt(pipe.charAt(k) + "");
							int dx = x + mx[m];
							int dy = y + my[m];

							if (isVaild(dx, dy) == true && isConnect(x,y,m,dx,dy)) {
								// 이동 가능
									isVisit[dy][dx] = 1;
									Queue[rear++] = new po(dx, dy);
								}
					}
					}
				}
			}
		}
	}

	public static int check() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (isVisit[i][j] == 1) {
					cnt++;
				}
				
			}
		
		}
		return cnt;
	}
	
	public static void isVisitPrint() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				
				System.out.print(isVisit[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void print(int a) {
		if (a == 0) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					System.out.print(map[i][j] + " ");
				}
				System.out.println();
			}
		}
	}

	public static boolean isVaild(int x, int y) {

		if (x < 0 || x > M - 1 || y < 0 || y > N - 1 || isVisit[y][x] == 1 || map[y][x] < 1)
			return false;
		else
			return true;

	}
	public static boolean isConnect(int x,int y, int di, int dx, int dy) {
		String cPipe = lists[map[y][x]];
		String nPipe = lists[map[dy][dx]];
		// cPipe == 01
		// nPipe == 03;
		
		// di == 1 -> 0있나 확인 0이면 1있나 확인
		// di == 2(좌) 면 우 있나 확인, 3 이면 2 있나 확인
		
		if(di == 1) // 아래로 내려가는중
		{
			for(int i = 0 ; i < nPipe.length(); i++) {
				if(nPipe.charAt(i) == '0')
					return true;
			}
		}else if(di == 0){
			for(int i = 0 ; i < nPipe.length(); i++) {
				if(nPipe.charAt(i) == '1')
					return true;
			}
			
		}else if(di == 2) {
			for(int i = 0 ; i < nPipe.length(); i++) {
				if(nPipe.charAt(i) == '3')
					return true;
			}
		}else if(di == 3) {
			for(int i = 0 ; i < nPipe.length(); i++) {
				if(nPipe.charAt(i) == '2')
					return true;
			}
		}
			return false;
		}

}

---

3. 맺음말

  ㆍ 체감난이도 : 쉬움
  ㆍ 파이프의 형태에 따라 이동가능한지 안한지만 체크해주면 간단한 BFS문제
  ㆍ 더욱 좋은 풀이방법이나 보완할 수 있는 부분, 또는 문제가 될 수 있는 부분들은 알려주시면 감사하겠습니다.