[프로그래머스 | Java Lv.2] [2021 카카오 채용연계형 인턴십] - 거리두기 확인하기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/81302?language=java#fn1

프로그래머스

---

 

최종 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
      static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};

    public static boolean bfs(int x, int y, String[] p) {
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[5][5];  // 방문 기록
        q.add(new int[]{x, y});
        visited[x][y] = true;

        while (!q.isEmpty()) {
            int[] pos = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = pos[0] + dx[i];
                int ny = pos[1] + dy[i];

                if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;

                // 맨해튼 거리 계산
                int manhattan = Math.abs(nx - x) + Math.abs(ny - y);

                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;

                    // 사람이 있을 경우, 맨해튼 거리 2 이내면 false 반환
                    if (p[nx].charAt(ny) == 'P' && manhattan <= 2) {
                        return false;
                    }

                    // 빈 테이블인 경우, 거리 2 이내일 때만 탐색을 계속
                    else if (p[nx].charAt(ny) == 'O' && manhattan < 2) {
                        q.add(new int[]{nx, ny});
                    }
                }
            }
        }

        return true;
    }

    public static int[] solution(String[][] places) {
        int[] answer = new int[5];

        // 5개의 테스트케이스
        for (int i = 0; i < 5; i++) {
            String[] p = places[i];
            boolean flag = false;

            // 2차원 배열을 돌면서 'P'가 나왔을 때 bfs를 진행
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    if (p[j].charAt(k) == 'P') {
                        if (!bfs(j, k, p)) {
                            flag = true;
                            break;
                        }
                    }
                }
                if (flag) break;
            }

            answer[i] = flag ? 0 : 1;
        }

        return answer;
    }
}

---

 

Reference

https://jisunshine.tistory.com/148

[level2] 프로그래머스 - 거리두기 확인하기(JAVA)