이번에 풀어본 문제는
프로그래머스 거리두기 확인하기 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Point
{
    int x,y,cnt;
    
    public Point(int x, int y, int cnt)
    {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}
class Solution {
    static Queue<Point> q;
    static int [] dx = {0,0,-1,1};
    static int [] dy = {1,-1,0,0};
    static boolean [][] isVis;
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        int answerIdx = 0;
        
        next : for(String [] str : places)
        {
            char [][] map = new char[5][5];
            for(int i = 0; i < 5; ++i)
            {
                char [] tmp = str[i].toCharArray();
                System.arraycopy(tmp,0,map[i],0,5);
            }
            
            for(int i = 0; i < 5; ++i)
            {
                for(int j = 0; j < 5; ++j)
                {
                    if(map[i][j] == 'P')
                    {
                        q = new LinkedList<>();
                        isVis = new boolean[5][5];
                        isVis[i][j] = true;
                        q.add(new Point(i,j,0));
                        if(!bfs(map)) // 안지켰을때 바로 컨티뉴
                        {
                            answer[answerIdx++] = 0;
                            continue next;
                        }
                    }
                }
            }
            answer[answerIdx++] = 1;
        }
        return answer;
    }
    static boolean bfs(char [][] map)
    {
        while(!q.isEmpty())
        {
            Point cur = q.poll();
            if(cur.cnt != 0 && map[cur.x][cur.y] == 'P')
            {
                if(cur.cnt <= 2) return false;
            }
            if(cur.cnt > 2) return true;
            for(int idx = 0; idx < 4; ++idx)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];
                
                if(!isValid(mx,my) || isVis[mx][my] || map[mx][my] == 'X') continue;
                isVis[mx][my] = true;
                q.add(new Point(mx,my,cur.cnt+1));
            }
        }
        return true;
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < 5 && y < 5;
    }
}

📝 풀이

5x5 크기의 대기실에서 각 응시자들 끼리 거리두기를 지키고 있는지 여부를 리턴하는 문제입니다.
다른 응시자(P)를 만나지 않은 상태에서 3칸이상 이동했다면 더이상 탐색할 필요가 없으므로 dfs보다는 bfs를 선택하여 풀어봤습니다.
먼저 탐색을 위해 String형태의 배열을 각 문자를 담은 char형 2차원 배열로 바꿔준 후, P의 위치를 기준으로 bfs를 진행합니다.
벽을 제외하고 모두 이동 가능하며, P를 만나지 않고 카운트가 2를 초과했을때는 옳다고 판단하여 true를 리턴해줍니다.
하지만 카운트가 2 이하일때 P를 만난다면 즉시 false를 리턴 후 다음 경우의수로 넘어갑니다.

📜 후기

dfs,bfs문제는 꽤 많이 풀어보아서 편하게 풀었던 것 같아요!
요즘 ide 의존을 줄이려고 프로그래머스 자체에서 풀고있는데, 제가 평소에 자동완성을 애용하다보니 조금씩 잔실수가 나오긴 하네요 ㅎㅎㅎㅎ 큰 지장은 없었지만 자꾸 훈련해서 익숙해져야겠습니다^~^