프로그래머스 level2) 거리두기 확인하기

링크 : 프로그래머스 level2) 거리두기 확인하기

문제

• 대기실(places) : 5x5 크기
• P : 응시자 자리
• O : 빈테이블
• X : 파티션
• 응시자들은 거리두리를 위하여 (r1, c1), (r2, c2)일 경우
  |r1 - r2| + |c1 - c2| > 2 이여야한다.
• 응시자들 사이에 파티션이 있을 경우 허용

출력 : 거리두리를 완벽하게 지키고 있을 경우 return 1 아니면 return 0

풀이

이 문제는 실제 코테에서 풀었던 문제~
쉽게 풀었던거 같다.
문제를 보면 DFS 유형이라는 것을 알수있다.

for문은 대기실을 차례대로 돈다.
이때 응시자가 있는 대기실을 발견한다면 DFS를 돌린다.
그 응시자 좌표 상하 좌우 좌표로 이동한다.
상하 좌우 좌표가

X라면 갈 필요가 없기때문에 돌아온다.
P라면 거리가 2이하인지 확인하고, 2이하이면 이미 거리두기 실패 이므로 전 메소드로 돌아가서 0을 리턴한다.
※여기서 주의 할점은 |r1 - r2| + |c1 - c2|==0일때는 자기 자신임으로 0을 리턴 하면 안된다.

구현

class Solution {
    static int ok;
	public static void dfs(int N, int j, int k, int x, int y, String[] places, boolean[][] check) {
		if (x < 0 || x >= N || y < 0 || y >= N)
			return;
		if (places[x].charAt(y) == 'X')
			return;
		if (check[x][y] == true)
			return;
		if (Math.abs(j - x) + Math.abs(k - y) > 2)
			return;
		if (Math.abs(j - x) + Math.abs(k - y) != 0 && places[x].charAt(y) == 'P') {
			ok = 0;
			return;
		}
		check[x][y] = true;
		dfs(N, j, k, x + 1, y, places, check);
		dfs(N, j, k, x - 1, y, places, check);
		dfs(N, j, k, x, y + 1, places, check);
		dfs(N, j, k, x, y - 1, places, check);
	}

	public static int checkPlace(String[] places, int N) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				boolean[][] check = new boolean[N][N];
				if (places[i].charAt(j) == 'P') {
					ok = 1;
					dfs(N, i, j, i, j, places, check);
					if (ok == 0)
						return 0;
				}
			}
		}
		return 1;
	}

    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
		int N = 5;
		for (int i = 0; i < places.length; i++)
			answer[i] = checkPlace(places[i], N);
		return answer;
    }
}