99클럽 코테 스터디 32일차 TIL, 프로그래머스 / 아이템 줍기

🔑 오늘의 학습 키워드 : bfs, 좌표 표현

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/87694

 

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    grid = [[0] * 101 for _ in range (101)]
    
    for x1,y1,x2,y2 in rectangle :
        x1, y1, x2, y2 = x1 * 2, y1 * 2, x2 * 2, y2 * 2
        for i in range (x1,x2+1):
            for j in range (y1,y2+1):
                grid[i][j] = 1

    for x1,y1,x2,y2 in rectangle :
        x1, y1, x2, y2 = x1 * 2, y1 * 2, x2 * 2, y2 * 2
        for i in range (x1+1,x2):
            for j in range (y1+1,y2):
                grid[i][j] = 0
        
    queue = deque([(characterX * 2,characterY * 2,0)])
    visited = set([(characterX * 2,characterY * 2)])
    dxs, dys = (-1,1,0,0) , (0,0,1,-1)
    
    def in_range (x,y):
        return 0<=x<101 and 0<=y<101
    
    while queue :
        x,y ,cnt= queue.popleft()
        for dx,dy in zip ( dxs, dys):
            nx,ny = x + dx , y + dy
            if in_range (nx,ny) and (nx,ny) not in visited and grid[nx][ny] == 1:
                queue.append((nx,ny,cnt+1))
                visited.add((nx,ny))
                
                if (nx,ny) == (itemX * 2,itemY * 2):
                    answer = cnt // 2 + 1
                    break
    
    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

테두리 부분을 1로 바꾸고, 해당 테두리를 따라가는 bfs를 구현하면 될 것 같았다.

 

⏰ 예상 시간 복잡도 O( V + E )

제한사항
rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
itemX, itemY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

 

😎 알고리즘 개요

1. 좌표 표현

 

우선 이 문제를 처음 풀때 하나의 좌표로 두고 풀어서 모서리 부분등이 잘 표현이 되지 않았다.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

그래서 이 부분을 개선하기 위해서 좌표를 2배로 늘려서  만들어 주어 그림을 구현했다.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 
0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 
0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 
0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

2. bfs 탐색

    queue = deque([(characterX * 2,characterY * 2,0)])
    visited = set([(characterX * 2,characterY * 2)])
    dxs, dys = (-1,1,0,0) , (0,0,1,-1)
    
    def in_range (x,y):
        return 0<=x<101 and 0<=y<101
    
    while queue :
        x,y ,cnt= queue.popleft()
        for dx,dy in zip ( dxs, dys):
            nx,ny = x + dx , y + dy
            if in_range (nx,ny) and (nx,ny) not in visited and grid[nx][ny] == 1:
                queue.append((nx,ny,cnt+1))
                visited.add((nx,ny))
                
                if (nx,ny) == (itemX * 2,itemY * 2):
                    answer = cnt // 2 + 1
                    break

 

이렇게 시작부터 끝 점 까지 탐새을 해주고 2배를 해줬으니 다시 축소를 시켜준다.

✅ 오늘의 회고

- bfs는 진 짜 잘한다.

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL