[프로그래머스] 거리두기 확인하기 문제풀이 python

🐒 문제

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

✍ 나의 풀이

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

def dfs(x,y,place,visited,step):
    if step == 2:
        return True
        # P로부터 2 맨해탄 거리 내에 다른 P 없음 -> 거리두기 만족
        
    visited[x][y] = True

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

        if 0 <= nx < 5 and 0 <= ny < 5:
            if place[nx][ny] != 'X' and not visited[nx][ny]:
                if place[nx][ny] == 'P':
                    return False
                    # 거리두기 실패
                else:
                    if visited[nx][ny]:
                        continue
                    if dfs(nx,ny,place,visited,step+1) == False:
                        return False

def search(place,visited):
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P' and not visited[i][j]:
                if dfs(i,j,place,visited,0) == False:
                    # 이번 place는 글러먹음
                    return False
    return True


def solution(places):
    answer = []
    for place in places:
        visited = [[False]*5 for _ in range(5)]

        if search(place,visited):
            answer.append(1)
        else:
            answer.append(0)
            
    return answer

45분 정도 걸린 문제,
문제에서 예시로 보여준 그림을 보고 DFS를 사용해야겠다고 떠올림

solution 함수에 모든 기능 구현하려다 가독성이 떨어져서
solution 함수 이외에 두개의 함수를 추가로 디파인해서 사용함

함수속에서 함수을 호출할때 보낸 인자에 리스트관계가 헷갈렸음

---

🧠 문제 이해

사용된 아이디어 : DFS, 방문확인, DFS 깊이 제한

거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.

전에 맨해튼 거리 관련문제를 풀어보았기 때문에 쉽게 이해할 수 있었다.

위 조건에 따르면

모든 응시자를 확인하여 응시자로 부터 두칸 이내에 다른 응시자가 있으면 거리두기가 실패한 것이고, 없으면 거리두기에 성공한 것이다.

그래서 나는 DFS의 깊이 제한이 필요하다고 생각했다.

방문확인 안되어있으면 DFS 탐색 중에 현재 응시생으로 돌아온다

---

코드

def solution(places):
    answer = []	# 각 시험장 거리두기 성공 여부를 담는 리스트
    for place in places:	# places에 다섯개의 응시실 정보가 들어있다. 하나씩 꺼낸다.
        visited = [[False]*5 for _ in range(5)]	# 새로운 시험장을 확인할때마다 행렬 방문정보를 초기화한다.

        if search(place,visited):	# 행렬 탐색을 했는데 모든 응시자가 거리두기에 성공했으면
            answer.append(1)
        else:	# 행렬 탐색중 거리두기에 실패한 경우가 발생하면
            answer.append(0)
            
    return answer

def search(place,visited):	# 응시실 정보와 방문기록을 파라미터로 받는다.
    for i in range(5):	
        for j in range(5):
        # 이중for문을 통해 5x5행렬을 탐색한다.
        	# (현재 응시실의 모든 자리를 탐색한다)
        
            if place[i][j] == 'P' and not visited[i][j]:	# 현재 확인한 자리에 응시자가 있으면
                if dfs(i,j,place,visited,0) == False:	# DFS로 탐색하여 거리두기가 실패했다면
                    return False
    return True	# 현재 응시실의 모든 자리를 탐색했는데 거리두기 위반자가 없으면

# 행렬의 세로축 가로축 탐색 방향을 지정하는 리스트
dx = [-1,0,0,1]
dy = [0,-1,1,0]

def dfs(x,y,place,visited,step):
# x : 세로축 좌표
# y : 가로축 좌표
# place : 현재 시험장 자리 정보
# step : 현재 DFS 깊이 (현재 응시자로 부터 몇칸 떨어졌는지)

    if step == 2:	# 현재 DFS 깊이가 2이면
        return True	 # 현재 응시자는 거리두기 성공
        
    visited[x][y] = True	# 현재 탐색한 위치 방문기록에 저장 

    for i in range(4):	# 현 위치에서 상하좌우 탐색하여 갈 곳 찾기
        nx = dx[i] + x
        ny = dy[i] + y

        if 0 <= nx < 5 and 0 <= ny < 5:	# 리스트 인덱스 초과 방지 
            if place[nx][ny] != 'X' and not visited[nx][ny]:	# 다음 갈 곳이 벽이 아니고, 방문한 적이 없으면
                if place[nx][ny] == 'P':	# 다음 갈 곳에 응시자가 있으면
                    return False
                    # 거리두기 실패
                else:	# 다음 갈 곳이 빈자리이면
                    if visited[nx][ny]:	# 이미 방문했던 곳이면 넘겨
                        continue
                    if dfs(nx,ny,place,visited,step+1) == False: # DFS했는데 거리두기에 실패한 사람이 있으면
                    		# DFS깊이가 증가했으로 step+1을 넘겨줌
                        return False