99클럽 코테 스터디 2일차 TIL(BFS)

📎 문제링크

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

프로그래머스

🤔 문제 이해 및 알고리즘 유형

알고리즘 유형

- BFS

💡 문제 해결 방법

1) 맵의 크기를 2배로 늘리고 사각형의 좌표 위치도 2배로 늘린다.

2) 맵에서 0은 내부로 1은 테두리로 설정한다.

3) BFS로 최단 거리를 탐색한다.

4) 이때 최종 답인 짧은 거리는 무조건 나누기 2를 해주어야 한다.

 

💻 코드

from collections import deque
def solution(rectangle, cx, cy, ix, iy):
    answer = 0
    graph = [[-1 for _ in range(102)] for _ in range(102)]
    visited = [[1 for _ in range(102)] for _ in range(102)]
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    
    #map에 라인채우기
    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: #내부
                    graph[i][j]=0
                elif graph[i][j]!=0: 
                    graph[i][j]=1 #테두리
    #bfs로 최단거리 탐색하기
    cx,cy,ix,iy=cx*2,cy*2,ix*2,iy*2
    queue=deque()
    queue.append((cx,cy))
    while queue:
        x,y=queue.popleft()
        if x==ix and y==iy:
            answer = visited[x][y]//2
            break
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if visited[nx][ny]==1 and graph[nx][ny]==1:
                visited[nx][ny]+=visited[x][y]
                queue.append((nx,ny))
                
    
    return answer

✔ 생각해봐야 할 점

- 맵을 2배로 늘려야 함

- 내부와 테두리를 어떻게 설정할 것인지 확인

- BFS로 최단거리 탐색하기

 

 

참고 사이트