프로그래머스 Lv.2 거리두기 확인하기 (Java / Python)

eora21·2022년 9월 7일

알고리즘 프로그래머스

프로그래머스

목록 보기

19/38

문제 링크

문제 간단 해석

현재 위치에서 2번 진행했을 때, 다른 사람이 있는지 없는지 확인하는 문제. 단, 벽으로 막혀있는 상태에선 진행할 수 없다.

Java

효율적이나 직관적이진 않은 코드.
현재 내 위치 주변을 둘러보고, 한번 이동 후 다음 위치를 보았을 때 P가 있는지 없는지를 확인하는 방식이다.
두 번 이동한 후 자기 자신이 무엇인지를 판단하는 방법이 오히려 가독성 면에서 좋을 수 있다.
다만, 내가 갈 수 있는 길인지 아닌지를 살펴보는 기준이 있기 때문에(O, X) 해당 기준도 생각할 겸 이러한 식으로 풀었다.
이해만 하고 넘어가도록 하자.

풀이 코드

import java.util.Arrays;

class Solution {
    private String[][] places;
    private int[][][] check = new int[5][5][5];
    private int[] dy = {0, 1, 0};
    private int[] dx = {1, 0, -1};
    
    public boolean isNotDistancing(int p, int y, int x, int step) {
        check[p][y][x] = step;
        int r, c;
        
        for (int to = 0; to < 3; to++) {
            r = y + dy[to];
            c = x + dx[to];
            
            if (0 <= r && r < 5 && 0 <= c && c < 5 && step < 2 && step + 1 < check[p][r][c]) {
                if (places[p][r].charAt(c) == 'P')
                    return true;
                else if (step == 0 && places[p][r].charAt(c) == 'O' && isNotDistancing(p, r, c, step + 1))
                    return true;
            }
        }
        
        return false;
    }
    
    public int[] solution(String[][] places) {
        this.places = places;
        int[] answer = {1, 1, 1, 1, 1};
        
        for (int p = 0; p < 5; p++)
            for (int i = 0; i < 5; i++)
                Arrays.fill(check[p][i], 3);
        
        place: for (int p = 0; p < 5; p++) {
            for (int r = 0; r < 5; r++) {
                for (int c = 0; c < 5; c++) {
                    if (places[p][r].charAt(c) == 'P' && isNotDistancing(p, r, c, 0)) {
                        answer[p] = 0;
                        continue place;
                    }
                }
            }
        }
        
        return answer;
    }
}

해석

this.places = places;
int[] answer = {1, 1, 1, 1, 1};

isNotDistancing 함수에서도 손쉽게 접근할 수 있도록, Solution 인스턴스 변수에 할당.
답은 미리 1로 다 넣어놓는다.

for (int p = 0; p < 5; p++)
    for (int i = 0; i < 5; i++)
        Arrays.fill(check[p][i], 3);

방문 체크를 하기 위한 check 배열 내의 값을 3으로 넣어준다. 안해줘도 무방. 대신 방문 체크 시 음수로 넣어주면 된다. 연습 겸 사용.

place: for (int p = 0; p < 5; p++) {
    for (int r = 0; r < 5; r++) {
        for (int c = 0; c < 5; c++) {
            if (places[p][r].charAt(c) == 'P' && isNotDistancing(p, r, c, 0)) {
                answer[p] = 0;
                continue place;
            }
        }
    }
}

return answer;

배열 내 값을 확인하는데, 만약 P를 찾게 되면 현재 배열 순서(p)와 찾은 위치를 넘긴다.
(p라는 변수명을 잘못 지은듯. 다음부터는 명확한 변수명을 사용해야겠다.)
만약 찾은 사람 주변에 타인이 있을 경우, 거리두기를 하지 않았으므로 answer 값을 0으로 바꾸고 다음 배열을 가져온다.

public boolean isNotDistancing(int p, int y, int x, int step) {
    check[p][y][x] = step;
    int r, c;
    
    for (int to = 0; to < 3; to++) {
        r = y + dy[to];
        c = x + dx[to];
        
        if (0 <= r && r < 5 && 0 <= c && c < 5 && step < 2 && step + 1 < check[p][r][c]) {
            if (places[p][r].charAt(c) == 'P')
                return true;
            else if (step == 0 && places[p][r].charAt(c) == 'O' && isNotDistancing(p, r, c, step + 1))
                return true;
        }
    }
    
    return false;
}

현재 도달한 위치에 따라 0과 1을 찍는다.
그 후 우, 하, 좌 방향을 탐색한다.
(윗방향은 탐색할 필요가 없다. 어차피 solution 내 for문에서 위에서부터 탐색해 내려오기 때문. 또한 방문 기록 상 현재 step보다 적게 들렸던 곳이라면 방문할 필요가 없다.)

탐색한 위치에 P가 있다면, 거리두기를 하지 않았으므로 true를 반환한다.
만약 내가 이동하지 않은 상태이며, 갈 수 있는 길이 있다면 해당 길로 이동 후 탐색한다.

둘 다 true를 반환하기 때문에, ||로 묶어 구성해도 된다.
극단적으로 한다면..

if (
    (0 <= r && r < 5 && 0 <= c && c < 5 && step < 2 && step + 1 < check[p][r][c]) &&
    (
        (places[p][r].charAt(c) == 'P') ||
        (step == 0 && places[p][r].charAt(c) == 'O' && isNotDistancing(p, r, c, step + 1))
    )
)
    return true;

이렇게 되겠지만 가독성이 처참해진다.
괄호 다 정리하면 깔끔해지긴 하나 코드의 흐름을 보기엔 더욱 더 힘들어진다.
생각의 흐름이 자연스러워지게끔 작성하자.

만약 다 둘러봤음에도 주변에 사람이 없다면, 거리두기를 위반하지 않은 것이므로 false 반환.

Python

풀이 코드

def solution(places):
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    
    def check(r, c):
        area = [[True] * 5 for _ in range(5)]
        area[r][c] = False
        stack = [(r, c, 1)]
        
        while stack:
            ro, co, step = stack.pop()
            
            for i in range(4):
                y = ro + dy[i]
                x = co + dx[i]
                
                if 0 <= y < 5 and 0 <= x < 5 and area[y][x]:
                    area[y][x] = False
                    if place[y][x] == "P":
                        return True
                    elif place[y][x] == "X":
                        continue
                    elif step < 2:
                        stack.append((y, x, step + 1))
    
    def make_result():
        for row in range(5):
            for col in range(5):
                if place[row][col] == "P":
                    if check(row, col):
                        return 0
        return 1
    
    result = []
    for place in places:
        result.append(make_result())
    
    return result

해석

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

...

result = []
for place in places:
    result.append(make_result())

return result

탐색할 네 방향 기준을 정하고, 해당 대기실에 따른 결과를 도출하도록 한다.

def make_result():
    for row in range(5):
        for col in range(5):
            if place[row][col] == "P":
                if check(row, col):
                    return 0
    return 1

row, col을 차례대로 탐색하다가 거리두기를 어겼다면 0을, 아니라면 1을 반환한다.
코드가 대각선으로 쭉 내려가는게 보기 불편하다면 if place[row][col] != "P": continue 를 사용하여 끊어주도록 하자.

def check(r, c):
    area = [[True] * 5 for _ in range(5)]
    area[r][c] = False
    stack = [(r, c, 1)]
    
    while stack:
        ro, co, step = stack.pop()
        
        for i in range(4):
            y = ro + dy[i]
            x = co + dx[i]
            
            if 0 <= y < 5 and 0 <= x < 5 and area[y][x]:
                area[y][x] = False
                if place[y][x] == "P":
                    return True
                elif place[y][x] == "X":
                    continue
                elif step < 2:
                    stack.append((y, x, step + 1))