2022.03.03 [백준] (python 파이썬) 경비원

 

 

 

 

 

https://www.acmicpc.net/problem/2564

2564번: 경비원

---

풀이

아래의 문제는 조건이 상당히 많은거같다...

우선 입력받은 좌표의 조건을 보면

• x가 1일 때, 북쪽 즉, (0,y), x가 2일 때, 남쪽 (m,y)
• x가 3일 때, 서쪽 (y,0), x가 4일 때, 동쪽 (y,n)

총 4가지 조건에 맞게 좌표를 설정해 배열에 담았다.

이후 동근이의 좌표가 배열의 제일 마지막에 들어갔기때문에 pop을 이용해서 깨내준다.

동근이가 상점으로 갈때 가로지르지 못하고 외각으로 돌아야 하기 때문에 각 조건을 나누었다.

1. 상점이 북쪽 혹은 남쪽일때
   1. 동근이가 상점과 같은 직선, 즉 북쪽에 같이 있거나 남쪽에 같이 있을때
   2. 동근이가 상점과 하나의 모서리를 두고 있을때, 즉 상점이 북쪽이면 동근이는 동쪽 또는 서쪽
   3. 동근이가 상점과 반대편(맞은편)에 있을때
2. 상점이 동쪽 혹은 서쪽에 있을때
   1. 동근이가 상점과 같은 직선에 있을때
   2. 동근이가 상점과 하나의 모서리를 두고 있을때
   3. 동근이가 상점과 반대편에 있을때

위의 조건으로 나누어 생각했다. 

• 만약 1-1번일때 x의 좌표는 같으므로 y좌표의 차이를 구해주면 이동거리가 된다. 이 때, 둘 중 어느 좌표가 클지 모르기때문에 절대값을 이용해 구해주었다.
• 1-2번일때 아까와 같이 x,y가 0일지 m,n일지 모르기 때문에 좌표를 빼준뒤 절대값을 이용했다.
• 1-3번의 경우 반대편에 있기 때문에 m만큼은 무조건 이동해야한다. 그리고 오른쪽으로 돌아야 빠른지 왼쪽으로 돌아야 빠른지 알기위해 min함수를 이용해 더 짧은 거리를 저장했다.

2번도 위와 동일하게 하여 동준이가 모든 상점으로 갈 수 있는 최단거리를 모두 더한 값을 구했다.

 

import math
from collections import deque
 
n,m=map(int, input().split())
k=int(input())
arr=deque()
for i in range(k+1):
    x,y=map(int,input().split())
    #북쪽일때
    if x==1:
        arr.append((0,y))
    #남쪽일때
    elif x==2:
        arr.append((m,y))
    #서쪽일때
    elif x==3:
        arr.append((y,0))
    #동쪽일때
    elif x==4:
        arr.append((y,n))
 
dis=0
#동근이의 좌표
nx,ny=arr.pop()
while arr:
    #상점의 좌표
    x,y=arr.pop()
    #상점이 북쪽 or 남쪽일때
    if x==0 or x==m:
        #동근이가 상점과 같은 선상에 있을때
        if nx==x:
            dis+=abs(ny-y)
        #동근이가 상점과 하나의 모서리를 두고있을때
        #예) 상점 북, 동근 동or서
        elif ny==0 or ny==n:
            dis+=abs(nx-x)+abs(ny-y)
        #동근이가 상점과 반대편(맞은편)에 있을때
        else:
            dis+=m+min((y+ny),(2*n-y-ny))
    #상점이 동쪽 or 서쪽에 있을때
    elif y==0 or y==n:
        #동근이가 상점과 동일 선상에 있을때
        if ny==y:
            dis+=abs(nx-x)
        #동근이가 상점과 하나의 모서리를 두고잇을때
        elif nx==0 or nx==m:
            dis+=abs(nx-x)+abs(ny-y)
        #동근이가 상점과 반대편(맞은편)에 있을때
        else:
            dis+=n+min((x+nx),(2*m-x-nx))
print(dis)