피곤..스터디 쉬고 싶은 하루다 🥲

코드가 개발새발이지만

문제 이해하기

• 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있는 경우가 잘 이해되지 않는다.
  

• 맨해튼 거리가 2 이하인 경우 “ 어느정도 막혀있어야지" 허용되는걸까?
  • 두 응시자 사이에, 경로 길이 2인 path 가 존재하지 않는 경우라고 생각해 볼 수 있을 것 같다.-> dfs던 bfs 던 사용하면 된다.
• 문제에서는 String[][] places 로 입력을 주어진다.
  • places[idx] 는 하나의 대기실에 대한 정보다 places[idx][row] 는 하나의 대기실의 row 행에 대한 정보다

문제 풀이하기

• String[] 에서 r행, c 열 → String[r].charAt(c)
• 하나의 응시자로부터 시작하여
  • 1. 경로 길이가 2이하일 때 까지
  • 2. 막에 가로막히지 않을 때 까지

    → 이동하였을 때 만나는 응시자가 없는 경우, 방문처리를 합니다

• 모든 응시자로부터 맨해튼 거리 2인 곳을 방문해 보아야 한다.
  • 이런 방문을 마친 응시자(시작점이 되어본 적이있는 응시자) 만 visit true 한다

교육에 들어오고 코테를 거의 안 풀었더니 문제 푸는데 오랜 시간이 걸리고 코드 가독성이 매우 떨어진당..ㅠㅠ

public class Main {
	private static int LEN = 5;
	private boolean[][] starts; //
	private int[][] move = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

	public int[] solution(String[][] places) {
		int[] answer = {};
		starts = new boolean[LEN][LEN];

		answer = checkRoom(places);

		return answer;
	}

	public int[] checkRoom(String[][] places) {
		int[] ans = new int[5];
		int roomNumb = 0;
		boolean success = false;

		for (String[] room : places) {
			// 방문 초기화
			initBoolArr(starts);
			success = true;
			// 각 방의 , 각 응시자가 시작점이 되어 수행한다
			for (int r = 0; r < LEN; r++) {
				for (int c = 0; c < LEN; c++) {
					if (room[r].charAt(c) != 'P' || starts[r][c] == true)
						continue;
					// 응시자인경우
					// 거리두기 실패한 경우
					if ((success = isSuccess(r, c, room)) == false) {
						ans[roomNumb] = 0;
						success = false;
						break;
					}
				}
				if (!success)
					break;
			}
			if (success) {
				ans[roomNumb] = 1;
			}
			roomNumb++;
		}

		return ans;
	}

	// 각 대기실 마다 visit 을 초기화해줘야 합니다
	public void initBoolArr(boolean[][] arr) {
		for (int i = 0; i < LEN; i++) {
			Arrays.fill(arr[i], false);
		}
	}

	// r,c 에서 시작하여 맨해튼 거리 2 내의 경로에 다른 응시자가 존재하는지 확인
	public boolean isSuccess(int r, int c, String[] room) {
		LinkedList<int[]> q = new LinkedList<>();
        // 각 출발점마다 visit 은 초기화되어야 합니다
		boolean[][] visit = new boolean[LEN][LEN];


		q.addLast(new int[] {r, c, 0}); // row, column , depth
		visit[r][c] = true;

		// bfs 상으로는 depth 가 2 이하인 범위 내에서 존재하면 안 되는 것
		while (!q.isEmpty()) {
			int[] cur = q.pollLast();

			for (int dir = 0; dir < move.length; dir++) {
				int nr = cur[0] + move[dir][0];
				int nc = cur[1] + move[dir][1];
				// 범위 초과
				if (nr < 0 || nc < 0 || nr >= LEN || nc >= LEN)
					continue;
				// 이미 방문한 경우
				if (visit[nr][nc])
					continue;
				// 칸막이가 있는 경우
				if (room[nr].charAt(nc) == 'X')
					continue;
				// 현재 노드까지의 거리가 2
				if (cur[2] >= 2) continue;
				// 다른 응시자를 만난 경우
				if (room[nr].charAt(nc) == 'P' ) {
					return false;
				}
				// 다른 응시자를 만나지 않은 경우
				visit[nr][nc] = true;
				q.addLast(new int[] {nr, nc, cur[2] + 1});
			}
		}
		return true;
	}
 }

그런데 이 문제에서
// 현재 노드까지의 거리가 2
if (cur[2] >= 2) continue;
이 부분 대신

public boolean isSuccess(int r, int c, String[] room) {
		LinkedList<int[]> q = new LinkedList<>();
		boolean[][] visit = new boolean[LEN][LEN];


		q.addLast(new int[] {r, c, 0}); // row, column , depth
		visit[r][c] = true;

		// bfs 상으로는 depth 가 2 이하인 범위 내에서 존재하면 안 되는 것
		while (!q.isEmpty()) {
			int[] cur = q.pollLast();
			// 💥 여기서 확인한다고 생각했는데 이렇게 하면 틀렸습니다가 나온당
			if (cur[2] >= 2)
				break;
			for (int dir = 0; dir < move.length; dir++) {
				int nr = cur[0] + move[dir][0];
				int nc = cur[1] + move[dir][1];
				// 범위 초과
				if (nr < 0 || nc < 0 || nr >= LEN || nc >= LEN)
					continue;
				// 이미 방문한 경우
				if (visit[nr][nc])
					continue;
				// 칸막이가 있는 경우
				if (room[nr].charAt(nc) == 'X')
					continue;
				// 다른 응시자를 만난 경우
				if (room[nr].charAt(nc) == 'P') {
					return false;
				}
				// 다른 응시자를 만나지 않은 경우
				visit[nr][nc] = true;
				q.addLast(new int[] {nr, nc, cur[2] + 1});
			}
		}
		return true;
	}

이렇게 하면 테스트 케이스 31 번만 틀렸습니다가 나오더라.
졸려서 이유를 생각하고 싶지 않다

---

누워서 생각해보니 위의 경우는 break 를 했기 때문에 문제가 되는거였다
if (cur[2] >= 2)
break; -> continue; 로 변경해주면 정답이 된다