[DFS/BFS] 아이템 줍기 (파이썬) - 진행 중

문제 설명

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

프로그래머스

문제 풀이

• gr에는 직사각형들의 변에 해당하는 좌표들에 넘버를 달아줌. (0번째 rec면 그 변 좌표들에 gr[x][y].append(0) )
• inner 라는 그래프를 따로 만들어서 해당 직사각형안에 있는 모든 좌표들에 True값을 부여해줌 
  1. 현재 위치 x,y 의 직사각형 넘버를 따온다.
  2. 다음으로 이동 할 수 있는 nx,ny 의 gr값(직사각형 넘버)이 이전 x,y에서의 넘버와 같고 gr의 길이가 1이라면 해당 직사각형의 같은 변을 타고 있으므로 큐에 담아주면 됨.
  3. 만약 gr[nx][ny]의 길이가 2 이상이라면, 다른 직사각형이 껴들어서 갈라지는 부분인 것이므로 조건문을 통해 테두리 바깥으로 이동하게끔 잡아줘야 함.
     • 변이 갈라지는 (x,y) => (nx,ny) 로 이동 했다면 큐에는 이 점은 변이 갈라지는 꼭지점이라는 것을 알려줄 dot값 1과 어떤 직사각형을 타고 왔는지 넘버를 알려줄 pre에 넘버를 담아줌.
       • q ( 꼭지점의 gr[nx][ny] 넘버, nx,ny, 1, pre 넘버 )
       • gr[nx][ny]넘버는 pre 넘버와 겹치면 안되므로 for문을 통해서 걸러주면 됨
     • 이후 큐에서 이 요소를 꺼낸 후 ( 변이 갈라지는 꼭지점 요소, dot==1 ) 직사각형이 겹쳐지는 부분(내부)은 inner 그래프를 통해 거를 수 있음.
     • 만약 현재 새로운 직사각형 넘버가 3이고 이전 넘버가 2인 직사각형에서 왔다면 내부로 겹쳐지는 inner[nx][ny][2] == True 인 좌표는 방문하면 안됨. 
       • 이 때, 다음 좌표도 꼭지점이 될 수 있으므로 이 점도 gr[nx][ny]의 길이가 2이상 인 것으로 판별해서 넣어줌
  4. 만약 첫 출발 지점이 꼭지점 일 경우도 위와 동일한 로직으로 출발 지점을 잡아주면 됨 ( 이렇게까지 했을 때 100점 만점 중 76 점 받음 )

소스 코드

오답 노트

• 예제에 제시된 테케를 고려해서 코드를 짬 ( 70.0 / 100 ) 
• 출발 지점이 변에 의해 갈라지는 부분인지 아닌지 고려해서 코드를 짜봄 ( 76.4 / 100 )  

from collections import deque


def solution(rec, chx, chy, ix, iy):
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    INF = int(1e9)
    answer = INF
    gr=[[[] for j in range(51)] for i in range(51)]
    inner = [[[False]*len(rec) for i in range(51)]for j in range(51)]
    for i in range(len(rec)):
        ax,ay=rec[i][0],rec[i][1]
        cx,cy=rec[i][2],rec[i][3]
        for j in range(ay,cy+1):
            gr[ax][j].append(i)
            gr[cx][j].append(i)
        for j in range(ax+1,cx):
            gr[j][ay].append(i)
            gr[j][cy].append(i)
        for j in range(ax,cx+1):
            for k in range(ay,cy+1):
                inner[j][k][i]=True

    visited = [[INF]*51 for i in range(51)]
    visited[chx][chy]=0
    q = deque()
    if len(gr[chx][chy])==1:
        q.append((gr[chx][chy][0],chx,chy,-1,gr[chx][chy][0]))
    else:
        for cur in gr[chx][chy]:
            for a in gr[chx][chy]:
                if a!=cur:
                    other=a
            for i in range(4):
                ccx=chx+dx[i]
                ccy=chy+dy[i]
                if ccx<=0 or ccy<=0 or ccx>50 or ccy>50:
                    continue
                if gr[ccx][ccy]==[]:
                    continue
                if inner[ccx][ccy][other]==True:
                    continue

                if len(gr[ccx][ccy])==1 and gr[ccx][ccy][0]==cur:
                    q.append((cur,ccx,ccy,-1,cur))
                    visited[ccx][ccy]=1
                
                if len(gr[ccx][ccy])>=2:
                    for j in gr[ccx][ccy]:
                        if j==cur:
                            continue
                        q.append((j,ccx,ccy,1,cur))
                        visited[ccx][ccy]=1

                
                

    while(q):
        cur, x,y,dot,pre = q.popleft()
        # print("cur:",cur,"   x:",x,"  y:",y,"  dot:",dot,"   pre: ",pre)
        # print(visited[x][y])
        # print("==================")
        if [x,y]==[ix,iy]:
            answer=min(answer,visited[x][y])
            continue
            
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<=0 or ny<=0 or nx>50 or ny>50:
                continue
            if gr[nx][ny]==[]:
                continue
            if visited[nx][ny]<visited[x][y]+1:
                continue
            
            if dot==1:
                if inner[nx][ny][pre]==False:
                    if len(gr[nx][ny])>=2:
                        for j in gr[nx][ny]:
                            if j==cur:
                                continue
                            q.append((j,nx,ny,1,cur))
                            visited[nx][ny]=visited[x][y]+1
                    else:
                        q.append((cur,nx,ny,-1,cur))
                        visited[nx][ny]=visited[x][y]+1
            else:
                if len(gr[nx][ny])==1 and gr[nx][ny][0]==cur:
                    q.append((cur,nx,ny,-1,cur))
                    visited[nx][ny]=visited[x][y]+1

                if len(gr[nx][ny])>=2:
                    for j in gr[nx][ny]:
                        if j==cur:
                            continue
                        q.append((j,nx,ny,1,cur))
                        visited[nx][ny]=visited[x][y]+1
            
    return answer

print(solution([[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]],3,4,7,8))