[Python/프로그래머스]거리두기 확인하기_[BFS]

 

 

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

프로그래머스

 

 

🐾 20221022 - 이번엔 혼자 못품..

 

 

으아아아 

혼자 풀었다!!!!

 

 

 

 

 

생각한 방법 :

매번 p가 나올 때 마다 bfs를 돌려서
2 이내에 다른 p가 발견되면 answer에 0을 넣자.

 

 

 

코드 : 

from collections import deque 
import copy 

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


def bfs(q,vis,tmp) :
    isTrue = 1 
    while q : 
        x,y,cost = q.popleft()
            # 동, 서, 남, 북 다 가봐야죠 
        for dir in range(4) :
            nx,ny = x + dx[dir], y + dy[dir]
            # 대기실 안, 2번만에 이동, 방문한적 없는 
            if 0<=nx<5 and 0<=ny<5 and cost+1 <=2 and vis[nx][ny] == 0:
            	# 사람이 있다? 
                if tmp[nx][ny] == 'P' : 
                    isTrue=0
                # 빈자리면 덱에 넣어요 
                elif tmp[nx][ny] == 'O' :
                    q.append([nx,ny,cost+1])
                    vis[nx][ny] = 1
    return isTrue 

def solution(places):
    answer = []
    for room in places :
        tmp = []
        q = deque()
        vis = [[0]*5 for _ in range(5)]
        for i in room :
            tmp.append(list(i))
        ifroomTrue = 1
        for i in range(5) :
            for j in range(5) :
            	#  사람을 발견해서 q에 넣을 때마다 BFS를 돌린다. 
                if tmp[i][j] == 'P' :
                    q.append([i,j,0])
                    vis[i][j] = 1 
                    if bfs(q,copy.deepcopy(vis),tmp)==0 : ifroomTrue = 0 
                    vis[i][j]  = 0
        answer.append(1) if ifroomTrue else answer.append(0)          
                
    return answer

 

 

 

다 맞긴했는데 효율성은 떨어질듯...ㅎㅎ 

 

 

 

 

 

 

 

BFS함수에서 isTrue를 만드는 대신 바로 return하면 조금 빠르다. 

 

from collections import deque 
import copy 

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


def bfs(q,vis,tmp) :
    while q : 
        x,y,cost = q.popleft()
            # 동, 서, 남, 북 다 가봐야죠 
        for dir in range(4) :
            nx,ny = x + dx[dir], y + dy[dir]
            if 0<=nx<5 and 0<=ny<5 and cost+1 <=2 and vis[nx][ny] == 0:
                if tmp[nx][ny] == 'P' : 
                    return 0
                elif tmp[nx][ny] == 'O' :
                    q.append([nx,ny,cost+1])
                    vis[nx][ny] = 1
    return 1

def solution(places):
    answer = []
    for room in places :
        tmp = []
        q = deque()
        vis = [[0]*5 for _ in range(5)]
        for i in room :
            tmp.append(list(i))
        ifroomTrue = 1
        for i in range(5) :
            for j in range(5) :
                if tmp[i][j] == 'P' :
                    q.append([i,j,0])
                    vis[i][j] = 1 
                    if bfs(q,copy.deepcopy(vis),tmp)==0 : ifroomTrue = 0 
                    vis[i][j]  = 0
        answer.append(1) if ifroomTrue else answer.append(0)          
                
    return answer

 

 

 

---

 

 

 

매번 list로 바꿔주는게 한번에 list로 이렇게 바꿔주면 시간을 줄어들듯! 

for p in places :
        for i in range(5):
            p[i]=list(p[i])

 

 

시간 조금 덜 걸리는 코드 :

from collections import deque 
import copy 
dx = [0,1,0,-1]
dy = [1,0,-1,0]

def bfs(q, vis, p) :
    while q :
        x,y,cnt = q.popleft()
        for dir in range(4) :
            nx,ny = x + dx[dir], y + dy[dir]
            if 0<=nx<5 and 0<=ny<5 and cnt < 2 and vis[nx][ny] == 0 :
                if p[nx][ny]=='O' : 
                    q.append([nx,ny,cnt+1])
                    vis[nx][ny] = 1 
                elif p[nx][ny] =='P' :
                    return 0
    return 1

def solution(places):   
    answer = []
    for p in places :
        for i in range(5):
            p[i]=list(p[i])
    for p in places :
        q = deque()
        vis = [[0]*5 for _ in range(5)]
        isokay = True
        for i in range(5) :
            for j in range(5) :
                # 응시자가 있다면 
                if p[i][j]=='P' :
                    q.append([i,j,0])
                    vis[i][j] = 1 
                    if bfs(q,copy.deepcopy(vis),p)==0 : isokay=0
                    vis[i][j] = 0
        answer.append(1) if isokay else answer.append(0)          
    return answer

 

 

확실히 덜 걸린다! 

 

 

---

 

 

시간을 더 줄이고 싶다면 

안지키는 시험장을 발견했을 때 break하도록 만들면 된다. 

 

from collections import deque 
import copy

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

def bfs(q,vis,p) :
    while q :
        x,y,cnt = q.popleft()
        for i in range(4) :
            nx,ny = x + dx[i] , y + dy[i]
            if 0<=nx<5 and 0<=ny<5 and vis[nx][ny] == 0 and cnt<2 :
                if p[nx][ny] == 'P' : return 0 
                elif p[nx][ny] == 'O' : 
                    q.append([nx,ny,cnt+1])
                    vis[nx][ny] = 1 
    return 1 
def solution(places): 
    answer = []
    for p in places :
        for i in range(5) :
            p[i] = list(p[i])
    
    for p in places :
        q = deque()
        isokay = True 
        vis = [[0]*5 for _ in range(5)]
        for i in range(5) :
            for j in range(5) :
                if p[i][j] == 'P' :
                    q.append([i,j,0])
                    vis[i][j] = 1 
                    if bfs(q,copy.deepcopy(vis),p) ==0 : 
                        answer.append(0)
                        isokay = False 
                        break 
                    vis[i][j] = 0 
            if isokay == False : break 
        if isokay : answer.append(1)
                    
    return answer

시간은 줄어드는데 코드는 더러워진다. 🤭