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

프로그래머스 아이템 줍기

오늘의 문제는 DFS/BFS 문제!

생각보다 어떻게 풀어야할지, 외곽을 어떻게 알아내고 교차점을 어떻게 처리하는지가 가장 포인트가 되는 문제였던것 같다.

풀때까지 아직 해답을 잘 모르겠지만, 우선 72점정도 획득한 코드를 공유해 본다.

나의 코드

from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
    max_x=0
    max_y=0
    for x1,y1,x2,y2 in rectangle:
        max_x=max(max_x,x1,x2)
        max_y=max(max_y,y1,y2)
    graph=[[0 for _ in range(max_x+2)] for _ in range(max_y+2)]
    visited=[[False for _ in range(max_x+2)] for _ in range(max_y+2)]
    # 가장 밖에 것을 구하기만 하면 됨.
    
    for x1,y1,x2,y2 in rectangle:
        for i in range(x1,x2+1):
            for j in range(y1,y2+1):
                graph[j][i]+=1
    
    def find_out():
        queue=deque()
        queue.append([0,0])
        search=[[-1,0],[1,0],[0,-1],[0,1]]
        while queue:
            ri,ci=queue.popleft()
            for dr,dc in search:
                nr=ri+dr
                nc=ci+dc
                if 0<=nr<max_y+2 and 0<=nc<max_x+2 and not visited[nr][nc]:
                    visited[nr][nc]=True
                    if graph[nr][nc]:
                        graph[nr][nc]=-1
                    else:
                        queue.append([nr,nc])
    find_out()    
    
    def bfs(start,end):
        dist=[[0 for _ in range(max_x+2)] for _ in range(max_y+2)]
        r,c=start
        dist[r][c]=1
        queue=deque()
        queue.append(start)
        search=[[-1,0],[1,0],[0,-1],[0,1]]
        while queue:
            ri,ci=queue.popleft()
            Flag=False
            for dr,dc in search:
                nr=ri+dr
                nc=ci+dc
                if 0<=nr<max_y+2 and 0<=nc<max_x+2 and graph[nr][nc]==-1 and dist[nr][nc]==0:
                    dist[nr][nc]=dist[ri][ci]+1
                    queue.append([nr,nc])
                    Flag=True
                        
            if not Flag:
                for dr,dc in search:
                    nr=ri+dr
                    nc=ci+dc
                    if 0<=nr<max_y+2 and 0<=nc<max_x+2 and graph[nr][nc] and dist[nr][nc]==0:
                        count=0
                        for dr,dc in search:
                            mr=nr+dr
                            mc=nc+dc
                            if 0<=mr<max_y+2 and 0<=mc<max_x+2 and graph[mr][mc]==-1:
                                count+=1
                        if count==2:
                            dist[nr][nc]=dist[ri][ci]+1
                            queue.append([nr,nc])
        er,ec=end
        return dist[er][ec]-1
    return  bfs([characterY,characterX],[itemY,itemX])

회고

시간이 늦어 내일 확인할 예정인데, 아마 어떤 아이디어가 필요하거나, 어떤 부분에서 실수를 해서 만점이 안나오는 것 같다.

생각보다 bfs/dfs는 쉬운편이라고 생각했는데, 문제 이해 + 생각보다 까다롭게 만든 조건에서 어려움을 느꼈다.

내일은 답을 찾아보고, 어떤 방식으로 풀어야했는지 정리해볼 생각이다.