BOJ 백준 파이썬 16973 직사각형 탈출

 

중요 point

도형이 움직이는 문제였다.

좌표계 설정이 굉장히 중요한 문제다.

도형이 움직이고 좌표계를 설정하는

문제를 더 많이 풀어봐야

할 것 같은 느낌이다.

 

<문제 기본 이해>

*좌표계 설정하는법*

Sr, Sc= 출발 좌표 (가장 위에 있으면서 왼쪽에 있는 좌표다.)

ex) (1,1)=1행 1열

 

Fr,Fc= 도착 좌표(Sr,Sc가 도달해야하는 좌표다. 결국 직사각형의 가장 위에 있으며 왼쪽에 있는 좌표)

ex) (2,3)=2행 3열

 

N,M=격자판의 크기

N=행,W=열

->1X1의 격자판이라하면 점 하나 이루어져있고, 2X2는 점 4개로 이루어져있꼬 3X3은 점 9개로 이루어져있다.

한 변에 점 1개가 있으면 1,점 2개가 있으면 길이가 2, 한 변에 점 3개가 있으면 3, 4개가 있으면 4

(이는 직사각형과 동일)

EX)2X2

 

EX)3X3

 

EX)4X4

 

H,W=직사각형의 크기

H=행,W=열

 

코드 설계는

 

첫 좌표를 받는다 -> 직사각형을 이루는 각 점에 벽이 있나 없나 체크한다 -> 있으면 -1 출력 끝

->없으면 큐에 집어 넣는다 -> 큐에서 시작점을 꺼낸다->Sr,Sc를 위,아래,왼쪽,오른쪽 방향에 따라 4방향 탐색을 한다.

->직사각형을 이루는 각 점에 벽이 있나 없나 체크하여 없으면 큐에 집어 넣는다->

반복한다->dist 배열의 결과를 확인한다

 

이런 식으로 이루어져있고 가장 어렵고 헷갈리는 부분은 직사각형의 각 변에 벽이 있나 확인하는 부분이라 생각한다.

(Sr,Sc)에서 ㅡ 자 방향은 행은 그대로고 열만 바뀌니 board[Sx][j]에서 Sx는 고정 시키고 j만 Sy에서 직사각형의 열의 길이인 Sy+w-1까지 탐색해주면 된다.

ㅣ자 방향은 열은 그대로고 행만 바뀌니 board[j][Sy]에서 Sy는 고정 시키고 j만 Sx에서 Sx+h-1까지 탐색해주면 된다.

ex) w=2고 시작점 (1,1)이면 가장 오른쪽 점은 (1,2)이므로 Sy+w-1가 2인 것도 유념해야할 포인트다.

 

이 정도면 문제 풀이의 핵심은 다 다룬것이라 생각하며 코드 올립니다.

 

 

 

import sys
from collections import deque
from itertools import combinations
 
 
def check(Sx,Sy):
    for j in range(Sy,Sy+w):
       if board[Sx][j]==1:
           return -1
    for j in range(Sx,Sx+h):
           if board[j][Sy]==1:
            return -1
 
    for j in range(Sy,Sy+w):
          if board[Sx+h-1][j]==1:
             return -1
 
    for j in range(Sx, Sx+h):
     if board[j][Sy+w-1]==1:
           return -1
    
    return 1
 
 
 
if __name__=='__main__':
    #sys.stdin=open("input2.txt", "rt")
    
    n,m=map(int,input().split()) ##n=행,m=열
 
    board=[list(map(int,input().split())) for _ in range(n)]
 
    h,w,Sx,Sy,Ex,Ey=map(int,input().split()) ##h=행,w=열 ,(sx,sy)=시작점 (행,열) ,(ex,ey)=도착점 (행,열)
    Sx=Sx-1
    Sy=Sy-1
    Ex=Ex-1
    Ey=Ey-1
 
 
    dx=[-1,+1,0,0] #(위,아래,왼쪽,오른쪽)
    dy=[0,0,-1,+1]
    q=deque()
 
    dist=[[-1]*m for _ in range(n)]
    #print(n-h,m-w)
    if check(Sx,Sy)==1: ##첫 시작이 직사각형 이룬다면
        if Sx==Ex and Sy==Ey:
            print(0)
            exit()
        
        q.append((Sx,Sy))
        dist[Sx][Sy]=0
    else: ##직사각형을 못 이룬다면
        print(-1)
        exit()
 
    cnt=0
    while q:
            x,y=q.popleft()
 
            for k in range(4):
                Sx=x+dx[k]
                Sy=y+dy[k]
 
                if 0<=Sx<=n-h and 0<=Sy<=m-w:
                    if board[Sx][Sy]==0:
                        if dist[Sx][Sy]==-1:
                            if check(Sx,Sy)==1:
                                q.append((Sx,Sy))
                               # print(Sx,Sy)
                                dist[Sx][Sy]=dist[x][y]+1
 
    print(dist[Ex][Ey])