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

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

문제

해당 문제는 배열이 주어졌을 때 거리두기가 가능한지 아닌지를 구하는 문제로 대기실은 총 5개이며 각 대기실은 5 *5 크기이고, 거리두기는 맨해튼 거리가 2 이하인 경우 실패한 경우다. 단 응시자 사이에 파티션으로 막혀있으면 허용한다 즉 파티션이 있으면 그쪽으로 이동을 못한다는 소리.

조건

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P, O, X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

풀이

해당 문제는 dfs를 이용해서 해결했다. 처음 문제를 보고 생각을 해보다가 먼저 사람을 모두 큐에 담은 다음 하나씩 빼내면서 이동 범위가 2칸 이내 사람이 있는지 없는지 체크하는 방식으로 풀면 되겠다고 생각했다.

그래서 bfs를 이용해서 풀어보려고 했는데 몇몇 테케에서 틀렸다는 결과가 나왔고 그러던 중 생각했던 게 우선순위 큐를 이용하면 되겠다였는데, 방문 체크하는 부분에서 생각을 잘못해서 문제를 해결하지 못했다.

그러던 중 dfs를 이용하고 dfs에 들어갈 때 방문 체크 배열을 초기화해주면 되겠다고 생가했고 아래와 같은 로직으로 해결할 수 있었다.

1. 먼저 큐에 사람 정보를 담아준다. (좌표, 이동 횟수) 지금 생각해보면 그냥 좌표만 담아주면 됨

2. 큐에서 한 명씩 꺼내면서 bfs를 돌려준다. (여기서 방문 배열 초기화)

  2 - 1. bfs에 들어오면 먼저 가지치기를 실시, 이동 횟수와 현재 리턴 배열 값을 비교

  2 - 2. 4방을 탐색하면서 범위에 벗어나거나 파티션에 막혔거나 이미 방문했으면 다음 방향 탐색

  2 - 3. 갈 수 있는 곳이 사람이 있으면 리턴 배열을 -1로 변경시키고 리턴

  2 - 4. 위의 조건에 해당하지 않으면 dfs 돌림. 

3. 위와 같은 로직을 모두 수행하고 나면 리턴 배열 값을 체크해서 성공 실패 여부를 갱신

코드

import java.util.*;

class Solution {
	static int t;
	static boolean[][] visit;
	static char[][] arr;
	static int[] dy = { -1, 1, 0, 0 }, dx = { 0, 0, -1, 1 }, answer = new int[5];

	public int[] solution(String[][] places) {
		for (t = 0; t < 5; t++) {
			arr = new char[5][5];
			Queue<Node> q = new LinkedList<>();
			for (int i = 0; i < 5; i++) { // 1. 먼저 큐에 사람의 위치를 모두 담아준다. 큐에 데이터형은 좌표값과 이동횟수를 정하도록 했다.
				arr[i] = places[t][i].toCharArray();
				for (int j = 0; j < 5; j++) {
					if (arr[i][j] == 'P')
						q.offer(new Node(i, j, 0));
				}
			}
			while (!q.isEmpty()) { // 2. 큐에서 하나씩 빼내면서 bfs를 돌려준다. 이떄 방문체크 배열도 초기화 해줌
				visit = new boolean[5][5];
				Node n = q.poll();
				dfs(n.y, n.x, n.cnt);
			}
			answer[t] = answer[t] == -1 ? 0 : 1; // 테케의 리턴배열값이 -1이면 거리두기 실패 그렇지않으면 성공
		}

		return answer;
	}

	private void dfs(int y, int x, int cnt) {
		visit[y][x] = true;
		if (cnt >= 2 || answer[t] == -1) // 이동횟수와 리턴 배열의 값을 체크(이미 -1이면 거리두기 실패 가지치기)해서 조건을 만족하면 리턴
			return;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5 || arr[ny][nx] == 'X' || visit[ny][nx]) // 배열범위 벗어나거나, 파티션에 막혔거나, 이미 방문했거나
				continue;
			if (arr[ny][nx] == 'P') { // 사람을 만났으면 거리두기 실패 리턴 배열 -1로 변경
				answer[t] = -1;
				return;
			}
			dfs(ny, nx, cnt + 1);
		}
	}

	class Node {
		int y, x, cnt;

		Node(int y, int x, int cnt) {
			this.y = y;
			this.x = x;
			this.cnt = cnt;
		}
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드