18회차 스터디 준비

프로그래머스 

2021 카카오 채용연계형 인턴십 

 

[level 2] 거리두기 확인하기 - 81302

https://school.programmers.co.kr/learn/courses/30/lessons/81302#

프로그래머스

 

내가 처음 생각해본 풀이 방식은 dfs를 이용하여

오른쪽과 아래쪽만 체크하면서 모든 배열을 순회하면 된다고 생각했다

그래서 아래와 같이 코드를 짰다.

 

[실패한 코드]

public boolean check(String[] room, int y,int x,int cnt){
	if(cnt==3) return true;
	else if(x>=5 || y>=5) return true;
	else if(room[y].charAt(x)=='X') return true;

	if(room[y].charAt(x)=='P') return false;
	else{
		if(!check(room, y+1, x, cnt+1)){
			return false;
		}else if(!check(room, y, x+1, cnt+1)){
			return false;
		}
	}
	return true;
}

그러나 이런 방식은

O P

P X 

와 같은 형태를 검사하지 못한다.

---

따라서 4방향을 모두 검사해보고 방문한곳을 따로 체크해두면서 

확인하는 방식으로 바꿨다.

 

[통과한 코드]

import java.util.Arrays;

public class 카카오2021인턴십_거리두기확인하기_방법1 {
    public static void main(String[] args) {
        Solution sol = new Solution();

        String[][] places = new String[][]{{"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"}, {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"}, {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"}, {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"}, {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}};
        System.out.println(Arrays.toString(sol.solution(places)));
    }

    static class Solution {
        public int[] solution(String[][] places) {
            int[] answer = new int[]{1, 1, 1, 1, 1};
            int[] dx = new int[]{1, 0, -1, 0};
            int[] dy = new int[]{0, 1, 0, -1};

            for (int t = 0; t < 5; t++) {
                String[] room = places[t];
                boolean[][] visited = new boolean[5][5];
                //세로
                for (int y = 0; y < 5; y++) {
                    // 가로
                    for (int x = 0; x < 5; x++) {
                        if (room[y].charAt(x) == 'P') {
                            if (answer[t] == 0) break;
                            visited[y][x] = true;
                            for (int i = 0; i < 4; i++) {
                                int ny = y + dy[i];
                                int nx = x + dx[i];

                                if (!check(room, ny, nx, 1, visited)) {
                                    answer[t] = 0;
                                    break;
                                }
                            }
                        }
                        if (answer[t] == 0) break;
                    }
                    if (answer[t] == 0) break;
                }
            }
            return answer;
        }

        public static boolean check(String[] room, int y, int x, int cnt, boolean[][] visited) {
            int[] dx = new int[]{1, 0, -1, 0};
            int[] dy = new int[]{0, 1, 0, -1};
            if (cnt == 3) return true;
            else if (y < 0 || x < 0 || x >= 5 || y >= 5) return true;
            else if (room[y].charAt(x) == 'X') return true;
            visited[y][x] = true;

            if (room[y].charAt(x) == 'P') return false;
            else {
                for (int i = 0; i < 4; i++) {
                    int ny = y + dy[i];
                    int nx = x + dx[i];

                    if (ny < 0 || nx < 0 || nx >= 5 || ny >= 5) continue;
                    if (visited[ny][nx]) continue;
                    visited[ny][nx] = true;

                    if (!check(room, ny, nx, cnt + 1, visited)) return false;
                    visited[ny][nx] = false;
                }
            }
            return true;
        }
    }
}

이 방법 이외에 더 좋은 방법이 있을까 생각해봤는데

아래와 같은 방식도 있을 것 같다.

 

1. 모든 사람들의 좌표를 구한다.

2. 사람들간의 거리를 구한다

3. 거리가 1인경우 무조건 거리두기를 어긴다.

4. 거리가 2인경우 

4-1. 두 사람이 같은 행/열에 있는 경우

P  또는  PXP
X
P

위와 같이 두사람 사이에 파티션이 있어야 거리두기를 지킨다.

4-2. 두 사람이 다른 행/열에 있는 경우

PX
XP

위와 같이 두개의 파티션이 있어야 거리두기를 지킨다.

 

이러한 방식으로 코딩을 진행해보면

public class 카카오2021인턴십_거리두기확인하기_방법1 {
    public static void main(String[] args) {
        Solution sol = new Solution();

        String[][] places = new String[][]{{"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"}, {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"}, {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"}, {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"}, {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}};
        System.out.println(Arrays.toString(sol.solution(places)));
    }

    static class Solution {
        public int[] solution(String[][] places) {
            int[] answer = new int[]{1, 1, 1, 1, 1};
            for (int t = 0; t < 5; t++) {
                String[] rooms = places[t];
                List<Coordinate> coordinates = new ArrayList<>();

                for (int i = 0; i < 5; i++) {
                    String room = rooms[i];
                    for (int j = 0; j < 5; j++) {
                        if (room.charAt(j) == 'P') {
                            coordinates.add(new Coordinate(i, j));
                        }
                    }
                }

                for (int i = 0; i < coordinates.size(); i++) {
                    int y = coordinates.get(i).y;
                    int x = coordinates.get(i).x;
                    for (int j = i + 1; j < coordinates.size(); j++) {
                        int ny = coordinates.get(j).y;
                        int nx = coordinates.get(j).x;

                        if (!check(rooms, y, ny, x, nx)) {
                            answer[t] = 0;
                        }
                    }
                }
            }
            return answer;
        }
    }

    static class Coordinate {
        public int y;
        public int x;

        public Coordinate(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static public boolean check(String[] rooms, int y, int ny, int x, int nx) {
        int manhattan = Math.abs(y - ny) + Math.abs(x - nx);
        if (manhattan <= 1) {
            return false;
        } else if (manhattan == 2) {
            if (y == ny) {
                if (rooms[y].charAt(Math.min(x, nx) + 1) == 'X') {
                    return true;
                } else {
                    return false;
                }
            } else if (x == nx) {
                if (rooms[Math.min(y, ny) + 1].charAt(x) == 'X') {
                    return true;
                } else {
                    return false;
                }
            } else {
                if (x < nx) {
                    if (rooms[y].charAt(x + 1) == 'X' && rooms[ny].charAt(nx - 1) == 'X') {
                        return true;
                    } else {
                        return false;
                    }
                } else {
                    if (rooms[y].charAt(x - 1) == 'X' && rooms[ny].charAt(nx + 1) == 'X') {
                        return true;
                    } else {
                        return false;
                    }
                }
            }
        } else return true;
    }
}

위와 같이 해결할 수 있다.