[알고리즘_카카오 인턴] 거리두기 확인하기_bfs

[알고리즘_카카오 인턴] 거리두기 확인하기_bfs

 

정말 오랜 시간이 걸렸다.....

 

bfs로 풀었는데 내 방식대로 해서 답을 맞히는데 오랜시간이 걸렸다.

 

처음에 for문을 두 번 돌면서 place[i][j] =="P" 즉 사람일 때를 찾아 bfs를 실행하고나서 for문 둘 다 break하고 나머지 for문을 돌지 않는 방법이 떠오르지 않았다. 결국 이를 check라는 함수로 따로 빼서 해결했다. 그랬더니 반쯤 맞았다.

 

# 첫 시도

def solution(places):
    answer = []
    visited = [[0] * (5) for _ in range(5)]
    for place in places: # 5번
        for i in range(5):
            for j in range(5):
                if place[i][j] == "P":
                    bfs(i,j, place, visited)

 

# 두 번째 시도

def check(place):
    visited = [[0] * (5) for _ in range(5)]
    for i in range(5):
        for j in range(5):
            if place[i][j] == "P":
                if bfs(i,j, place, visited) == False:
                    return False
    return True


def solution(places):
    answer = []
    for place in places: # 5번
        if check(place):
            answer.append(1)
        else:
            answer.append(0)
    return answer

 

그 후 완성된 코드의 모습. 그런데 여기서 bfs 함수에서 cn1 += 1의 위치가 for i in range(4) 보다 앞에 있어야 하는데 뒤에 있어 오류가 났다. 이를 앞으로 옮겨 해결 했는데 다 맞고 test 9번만 틀리더라..

 

# 세 번째 시도

from collections import deque

def bfs(p,q, place, visited):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    cnt = 0
    queue = deque()
    visited[p][q] = 1
    queue.append([p,q,cnt])
    while queue:
        x,y,cnt1 = queue.popleft()
        cnt1 += 1 # 여기로 옮김
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            ## cnt1 +=1 # 여기서
            if 0 <= nx < 5 and 0 <= ny < 5:
                if visited[nx][ny] == 0 and place[nx][ny] != "X": # 방문하지 않았고 파티션 아닌 경우
                        if place[nx][ny] == "O": # 빈 테이블
                            visited[nx][ny] = 1
                            queue.append([nx,ny,cnt1])
                        else: # P 사람인 경우
                            if cnt1 <= 2: # 거리가 2이하인 경우. 
                                return False
                            else: # 거리가 3 이상인 경우. ㄱㅊ
                                visited[nx][ny] = 1
                                queue.append([nx,ny,0])
                            
    return True


def check(place):
    visited = [[0] * (5) for _ in range(5)]
    for i in range(5):
        for j in range(5):
            if place[i][j] == "P":
                if bfs(i,j, place, visited) == False:
                    return False
    return True


def solution(places):
    answer = []
    for place in places: # 5번
        if check(place):
            answer.append(1)
        else:
            answer.append(0)
    print(answer)
    return answer

 

정답 코드

check 함수 안에 있던 visited가 bfs 안으로 들어갔더니 test 9 하나가 통과되면서 다 통과 되었다. 틀렸던 이유는 특정 "P"로 시작된 bfs가 True로 return된 후 visited가 0값으로 초기화 되지 않고 다시 2중 for문을 돌아 다른 "P"로 bfs를 돌았을 때 에러가 났기 때문이다. 즉, 처음에는 bfs가 True로 return되고 이후 다른 "P"에서 False가 됐다는 얘긴데.. 이게 가능한건가...? test case가 어떤건지 볼 수 있었으면 좋겠다... 더 생각해보자 !

# 네 번째 시도

from collections import deque

def bfs(p,q, place):
    visited = [[0] * (5) for _ in range(5)]
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    cnt = 0
    queue = deque()
    visited[p][q] = 1
    queue.append([p,q,cnt])
    while queue:
        x,y,cnt1 = queue.popleft()
        # print(x,y, cnt1, visited)
        cnt1 +=1
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < 5 and 0 <= ny < 5:
                if visited[nx][ny] == 0 and place[nx][ny] != "X": # 방문하지 않았고 파티션 아닌 경우
                        if place[nx][ny] == "O": # 빈 테이블
                            visited[nx][ny] = 1
                            queue.append([nx,ny,cnt1])
                        else: # P 사람인 경우
                            if cnt1 <= 2: # 거리가 2이하인 경우. 
                                return False
                            else: # 거리가 3 이상인 경우. ㄱㅊ
                                visited[nx][ny] = 1
                                queue.append([nx,ny,0])
                            
    return True


def check(place):
    for i in range(5):
        for j in range(5):
            if place[i][j] == "P":
                if bfs(i,j, place) == False:
                    return False
    return True


def solution(places):
    answer = []
    for place in places: # 5번
        if check(place):
            answer.append(1)
        else:
            answer.append(0)
    return answer