81302 – Nextra

거리두기 확인하기

https://school.programmers.co.kr/learn/courses/30/lessons/81302#fn1 (opens in a new tab)

내 풀이 1

2번 풀이 작성 후 0의 사방에 P가 2개 이상 존재할 경우 거리두기가 지켜지지 않는다는 아이디어에서 착안한 풀이인데 이것도 틀렸다.

class Solution {
    public int[] solution(String[][] places) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
 
        for (String[] place : places) {
            if (bfs(place)) {
                ans.add(1);
            } else {
                ans.add(0);
            }
        }
 
        return ans.stream()
                .mapToInt(Integer::intValue)
                .toArray();
    }
 
    public boolean bfs(String[] place) {
        int Y = place.length;
        int X = place[0].length();
        int[][] direction = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
        for (int y = 0; y < Y; y++) {
            for (int x = 0; x < X; x++) {
                int cnt = 0;
                if (place[y].charAt(x) == 'O') {
                    for (int[] d : direction) {
                        int ny = y + d[0];
                        int nx = x + d[1];
                        if (!(-1 < ny && ny < Y && -1 < nx && nx < X)) break; // 범위 안에 속하지 않으면 break
                        if (place[ny].charAt(nx) == 'P') {
                            cnt++;
                        }
                    }
                }
                if (cnt >= 2) {
                    return false;
                }
            }
        }
        return true;
    }
}

내 풀이 2

import java.util.*;
 
class Solution {
    public int[] solution(String[][] places) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        
        // 각 대기실 별로 돌면서 확인
        for(String[] p: places) {
            if(checkAllPlaces(p)) {
                ans.add(1);
            }
            else {
                ans.add(0);
            }
        }
        
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public boolean checkAllPlaces(String[] place) {
        int[][] direction = {
            {2,0, 1,0}, 
            {1,1, 1,0, 0,1}, 
            {0,2,0,1}, 
            {-1,1,0,1,-1,0}, 
            {-2,0, -1,0}, 
            {-1,-1,-1,0,0,-1},
            {-2,0,-1,0},
            {1,-1,1,0,0,-1}
        };
        int Y = place.length;
        int X  = place[0].length();
        
        for(int y = 0; y < Y; y++) {
            for(int x = 0; x < X; x++) {
                if(place[y].charAt(x) == 'P') {
                    for(int[] d: direction) {
                        if(!isOutOfRange(place, new int[]{y + d[0], x + d[1]})) {
                            // 만약 정상적인 자리 배치라면 true 반환
                    		if(!bfs(place, new int[]{y,x}, d)) {
                                return false;
                            } 
                        }
                    }
                }
            }
        }
        return true;
    }
    
    public boolean bfs(String[] place, int[] curD, int[] d)  {
        int y = curD[0];
        int x = curD[1];
        boolean a = false;
        boolean b = false;
        if(d.length == 6) {
            a = place[y + d[0]].charAt(x + d[1]) != 'P';
            b = place[y + d[2]].charAt(x + d[3]) == 'X' && place[y + d[4]].charAt(x + d[5]) == 'X';
        } else {
            a = place[y + d[0]].charAt(x + d[1]) != 'P';
            b = place[y + d[2]].charAt(x + d[3]) == 'X';
        }
        if(a || b) {
            return true;
        } 
        return false;
	}
    
    public boolean isOutOfRange(String[] place, int[] nextD) {
        int MY = place.length;
        int MX = place[0].length();
        if(-1 < nextD[0] && nextD[0] < MY && -1 < nextD[1] && nextD[1] < MX) {
            return false;
        } 
        return true;
    }
}

정답

큐에 dist를 넣는 방식으로 거리 계산을 해결했다.

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        Arrays.fill(answer, 1);  // 기본적으로 거리두기를 지키고 있다고 가정
 
        for (int i = 0; i < places.length; i++) {
            String[] room = places[i];
            if (!checkRoom(room)) {
                answer[i] = 0;
            }
        }
 
        return answer;
    }
 
    private boolean checkRoom(String[] room) {
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
        for (int y = 0; y < 5; y++) {
            for (int x = 0; x < 5; x++) {
                if (room[y].charAt(x) == 'P') {
                    // BFS 시작
                    Queue<int[]> queue = new LinkedList<>();
                    boolean[][] visited = new boolean[5][5]; // boolean[] 배열은 false로 초기화 됨
                    queue.offer(new int[] {y, x, 0});  // 좌표와 시작점으로부터의 거리
                    visited[y][x] = true;
 
                    while (!queue.isEmpty()) {
                        int[] current = queue.poll();
                        int cy = current[0];
                        int cx = current[1];
                        int dist = current[2];
 
                        if (dist > 0 && dist <= 2 && room[cy].charAt(cx) == 'P') {
                            return false;
                        }
 
                        if (dist < 2) {
                            for (int[] dir : directions) {
                                int ny = cy + dir[0];
                                int nx = cx + dir[1];
                                if (ny >= 0 && ny < 5 && nx >= 0 && nx < 5 && !visited[ny][nx] && room[ny].charAt(nx) != 'X') {
                                    visited[ny][nx] = true;
                                    queue.offer(new int[] {ny, nx, dist + 1});
                                }
                            }
                        }
                    }
                }
            }
        }
        return true;
    }
}

괄호 회전하기 표 편집