[프로그래머스(Programmers)][자바(java)] (Lv2) 거리두기 확인하기 <2021 카카오 채용연계형 인턴십>

 

https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

 

문제 풀이

 

import java.util.*;

public class Solution {

	class Cell {
		int x, y, m; // manhattan distance
		Cell(int x, int y, int m) {
			this.x = x;
			this.y = y;
			this.m = m;
		}
	}

	int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 }; // directional

	public int[] solution(String[][] places) {
		final int l = 5; // length
		int r = places.length, s[][], i, j, k, cx, cy, nx, ny, nm, n; char c; 
		// room, structure, current/next x/y/m, number
		List<Cell> ls; // list
		Queue<Cell> qu; Cell cell; // queue
		boolean v[][]; // is visited
		int a[] = new int[r]; // answer
		outer: 
		for (k = 0; k < r; ++k) {
			s = new int[l][l];
			ls = new ArrayList<>();
			for (i = 0; i < l; ++i) {
				for (j = 0; j < l; ++j) {
					c = places[k][i].charAt(j);
					if (c == 'P') {
						ls.add(new Cell(i, j, 0));
						s[i][j] = 0;
					} else if (c == 'O')
						s[i][j] = 1;
					else
						s[i][j] = 2;
				}
			}
			if( ls.size() <= 1 ) {
				a[k] = 1;
				continue;
			}
			for (Cell cc : ls) {
				qu = new ArrayDeque<>();
				v = new boolean[l][l];
				qu.add(cc);
				v[cc.x][cc.y] = true;
				while (!qu.isEmpty()) {
					cell = qu.remove();
					cx = cell.x; cy = cell.y; nm = cell.m + 1;
					for (i = 0; i < 4; ++i) {
						nx = cx + dx[i]; ny = cy + dy[i];
						if (nx < 0 || nx >= l || ny < 0 || ny >= l || v[nx][ny])
							continue;
						n = s[nx][ny];
						if (n == 0)
							continue outer;
						if (n == 1) {
							if (nm >= 2)
								continue;
							qu.add(new Cell(nx, ny, nm));
						}
						v[nx][ny] = true;
					}
				}
			}
			a[k] = 1;
		}
		return a;
	}

	public static void main(String[] args) {
		System.out.println(Arrays.toString(solution(new String[][] { 
				{ "POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP" },
				{ "POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP" }, 
				{ "PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX" },
				{ "OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO" }, 
				{ "PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP" } })));
		// 10111
		System.out.println(Arrays.toString(solution(new String[][] { 
			{ "OOOOO", "OOOOO", "OOPOO", "OOOOO", "OOOOO" } })));
		// 1	// 응시자 1명
		
		System.out.println(Arrays.toString(solution(new String[][] { 
			{ "OOOOO", "OOPOO", "OOPOO", "OOOOO", "OOOOO" } })));
		// 0	// 맨해튼 거리 1
		System.out.println(Arrays.toString(solution(new String[][] { 
			{ "OOPOO", "OOOOO", "OOPOO", "OOOOO", "OOOOO" } })));
		// 0	// 맨해튼 거리 2
		System.out.println(Arrays.toString(solution(new String[][] { 
			{ "OOOOO", "OPOOO", "OOPOO", "OOOOO", "OOOOO" } })));
		// 0	// 맨해튼 거리 2 (대각선)
		
		System.out.println(Arrays.toString(solution(new String[][] { 
			{ "POOOO", "OOOOO", "OOPOO", "OOOOO", "OOOOO" } })));
		// 1	// 맨해튼 거리 3
		
		System.out.println(Arrays.toString(solution(new String[][] { 
			{ "OOPOO", "OOXOO", "OOPOO", "OOOOO", "OOOOO" } })));
		// 1	// 맨해튼 거리 2 [파티션]
		System.out.println(Arrays.toString(solution(new String[][] { 
			{ "OOOOO", "OPXOO", "OOPOO", "OOOOO", "OOOOO" } })));
		// 0	// 맨해튼 거리 2 (대각선) [파티션1개]
		System.out.println(Arrays.toString(solution(new String[][] { 
			{ "OOOOO", "OPXOO", "OXPOO", "OOOOO", "OOOOO" } })));
		// 1	// 맨해튼 거리 2 (대각선) [파티션2개]
	}
}

 

*  bfs

-  응시자 간 거리두기가 잘 되어있는지 확인하려면 한 응시자의 자리로부터 맨해튼 거리가 2 이하인 자리만 보면 됨
-  대기실을 5x5 크기의 2차원 격자로 보고, 각 응시자의 위치(x, y)로부터 너비우선탐색으로 셀 탐색
-  맨해튼 거리(m)는 응시자의 위치로부터 탐색한 셀의 개수와 같음

-  응시자의 위치와 맨해튼 거리( 이동 횟수 )의 상태를 담은 Cell 클래스 생성 ( int x, int y, int m )
-  대기실의 개수 int r  ( room = places.length ) 를 구하고, r개의 각 대기실의 거리두기 상태를 저장할 int a[] ( answer ) 생성 ( 0 <= k < r )
-  입력받은 대기실 구조 배열인 String[][] place의 값을 토대로 int[][] s 생성 ( structure )

설명	char	int
응시자	P	0
테이블	O	1
파티션	X	2

-  응시자들의 위치를 찾아 Cell 객체 생성 후 List<Cell> ls에 담음
-  응시자가 없거나 1명인 경우 거리두기가 지켜졌으므로 '1'

-  List<Cell> ls를 순회하며 각각의 응시자를 기준으로 맨해튼 거리가 2인 자리까지 너비우선탐색 진행
-  응시자의 자리( v[cc.x][cc.y] == 0 )와 인접한 자리( v[nx][ny] )에
   1)  다른 응시자( 0 )가 있는 경우  --  맨해튼 거리가 1이므로 거리두기 안 됨 ( a[k] = 0 )
   2)  테이블( 1 )이 있는 경우  --  맨해튼 거리 2 이내에 다른 응시자가 있는지 탐색하여 거리두기가 된 상태인지 확인해야 함
                                            ( 있으면 거리두기가 안 된 상태 ( a[k] = 0 ) )
   3)  파티션( 2 )이 있는 경우  --  거리두기가 된 상태( a[k] = 1 )이므로 더 이상 탐색을 안 해도 됨