[Python/프로그래머스]아이템 줍기_(BFS)

 

 

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

프로그래머스

 

 

🐾 20220924 

 

 

 

 

 

테두리 처리 어떻게하지....?

를 생각하다 모르겠어서 구글링했다.

생각보다 간단한 방법을 쓴다. 

내부일 경우 0으로 채우고 

내부가 아닌경우 0이 아닌지 확인하고(다른 도형의 내부인지) 둘 다 아니면 1을 저장해 모서리라는 것을 알려준다. 

 

 

 

그런데 다들 *2를 해서 왜들 이러나... 이해가 안됐는데 

아래 참고 블로그를 보고 단번에 이해했다.

경계선이 인접할 경우 의도하지 않은 최단거리가 발생해서 그런것이었다.

 

 

2배를 해서 구해주고 나중에 //2를 해준다. 

 

 

 

경계선은 다 돌면서 내부는 0으로 , 내부가 아니고 이전 도형의 내부가 아닐경우 테두리로 처리하여 filed를 만들어준다.

그리고 BFS~~!!

 

 

 

코드 : 

from collections import deque


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

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    field = [[-1] * 102 for i in range(102)]
    
    for r in rectangle :
        x1,y1,x2,y2 = map(lambda x : x*2, r)
        for i in range(x1,x2+1) :
            for j in range(y1,y2+1) :
                if x1 < i < x2 and y1<j<y2 :
                    field[i][j] = 0
                elif field[i][j] !=0 :
                    field[i][j] = 1 
        
    q = deque()
    q.append([characterX * 2, characterY * 2])
    vis = [[1] * 102 for i in range(102)]
    
    
    while q :
        x,y = q.popleft()
        if x == itemX*2 and y == itemY*2 :
            answer = vis[x][y] //2 
            break
        for k in range(4) :
            nx,ny = x + dx[k], y + dy[k]
            if field[nx][ny] ==1 and vis[nx][ny] == 1 :
                q.append([nx,ny])
                vis[nx][ny] = vis[x][y] +1 
                
        
    return answer

 

 

 

 

생각보다 간단한데 ... 2배를 하는 아이디어는 어떻게 떠올리지...신기하넹🧠

 

 

 

 

 

아주 약간 다른 코드 : 

from collections import deque


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

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    field = [[-1] * 102 for _ in range(102)]
    
    for r in rectangle :
        x1,y1,x2,y2 = map(lambda x : x*2,r)
        for i in range(x1,x2+1) :
            for j in range(y1,y2+1) :
                # 내부
                if x1<i<x2 and y1<j<y2 :
                    field[i][j] = 0 
                # 테두리 
                elif field[i][j] != 0 :
                    field[i][j] = 1
    q = deque([[characterX*2,characterY*2]])
    vis = [[-1] * 102 for _ in range(102)]
    vis[characterX*2][characterY*2] = 1 
    
    while q :
        x,y = q.popleft()
        if x == itemX*2 and y == itemY*2 :
            answer = (vis[x][y]//2)
            break 
        for i in range(4) :
            nx,ny= x + dx[i], y +dy[i]
            if 0<=nx<102 and 0<=ny<102 and vis[nx][ny] == -1 and field[nx][ny]==1 :
                q.append([nx,ny])
                vis[nx][ny] = vis[x][y] +1     
        
    return answer

 

 

 

 

참고 블로그 : 

https://velog.io/@rlaalswn3282/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%95%84%EC%9D%B4%ED%85%9C-%EC%A4%8D%EA%B8%B0

[프로그래머스] 아이템 줍기