[BOJ][⚪1][백준#02564] 경비원

문제 출처

BAEKJOON Online Judge #2564

문제

동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다. 예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. <그림 1>과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다.

< 그림 1 > 1번 상점에서 호출이 들어 왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가 된다. 마찬가지로 동근이의 위치에서 2번 상점까지의 최단 거리는 6, 3번 상점까지의 최단 거리는 5가 된다. 블록의 크기와 상점의 개수 및 위치 그리고 동근이의 위치가 주어질 때 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄에 하나씩 상점의 위치가 주어진다. 상점의 위치는 두 개의 자연수로 표시된다. 첫째 수는 상점이 위치한 방향을 나타내는데, 1은 블록의 북쪽, 2는 블록의 남쪽, 3은 블록의 서쪽, 4는 블록의 동쪽에 상점이 있음을 의미한다. 둘째 수는 상점이 블록의 북쪽 또는 남쪽에 위치한 경우 블록의 왼쪽 경계로부터의 거리를 나타내고, 상점이 블록의 동쪽 또는 서쪽에 위치한 경우 블록의 위쪽 경계로부터의 거리를 나타낸다. 마지막 줄에는 동근이의 위치가 상점의 위치와 같은 방식으로 주어진다. 상점의 위치나 동근이의 위치는 블록의 꼭짓점이 될 수 없다.

출력

첫째 줄에 동근이의 위치와 각 상점 사이의 최단 거리의 합을 출력한다.

예제

입력

10 5
3
1 4
3 2
2 8
2 3

출력

23

My Sol

def pos23(W, H, d, x):
    if d == 1:
        return x, H
    elif d == 2:
        return x, 0
    elif d == 3:
        return 0, H-x
    elif d == 4:
        return W, H-x

def dfs(cnt, ni, nj, ti, tj):
    if ni==ti and nj==tj:
        return cnt

    global mat
    mat[ni][nj] = 0
    didj = [(-1,0), (1,0), (0,1), (0,-1)]

    for di, dj in didj:
        if 0<=ni+di<(W+1) and 0<=nj+dj<(H+1):
            if mat[ni+di][nj+dj]:
                return dfs(cnt+1, ni+di, nj+dj, ti, tj)

W, H = map(int, input().split())
L = 2*(W+H)
N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]
nd, nx = map(int, input().split())

mat = [[1]*(H+1)]
mat += [[1]+[0]*(H-1)+[1] for _ in range(W-1)]
mat += [[1]*(H+1)]

sum_v = 0
for d, x in lst:
    mat = [[1]*(H+1)]
    mat += [[1]+[0]*(H-1)+[1] for _ in range(W-1)]
    mat += [[1]*(H+1)]

    ni, nj = pos23(W, H, nd, nx)
    ti, tj = pos23(W, H, d, x)

    k = dfs(0, ni, nj, ti, tj)
    ans = k if L > 2*k else L-k
    sum_v += ans
print(sum_v)

사방의 방향을 숫자로 주는 것을 처리하는 것이 번거로운 문제이다. 우선 선 위에 있는 좌표점을 공간으로 취급하기 위해서 입력받은 가로, 세로에 1씩을 더하는 크기의 2차원 배열 mat을 정의하였다. 중앙은 0, 사방은 1로 하여 나중에 길을 찾는 벡터를 검색하는 경우 0이 아닌 곳을 체크하도록 하였다.

각 좌표들을 lst에 담고, 이를 하나하나 꺼내 어느 쪽 변에 있는지, 그리고 기준점으로부터 얼마나 떨어져있는지를 체크하여 좌표상에 체크하였다. 변의 숫자와 기준점으로부터의 거리를 전달하면 좌표상의 행렬값을 반환하는 함수 pos23을 작성하여 현재 위치와 목적지의 위치를 행렬값으로 받아왔다. 이후 현재 위치를 기준으로 상하좌우 중 범위를 넘지 않으면서 값이 0이 아닌 곳으로 하나씩 전진해나간다. 그러면서 목표하는 좌표에 도착하면 그때의 이동한 카운트 변수를 반환하는 것이다.

그런데 이는 최단거리가 아닌, 단방향으로 이동하는 방식이었다. 그 이유는 어차피 블럭을 모두 돌기 때문에 bfs로 양쪽을 체크하는 것이 더 비효율적이라고 생각했으며, 막다른 길이 나와서 돌아갈 일도 없기 때문에 visit도 사용하지 않았다. 이렇게 카운트가 나오면 전체 둘레와 비교하면 된다. 만약 카운트의 2배가 둘레보다 크면 절반을 넘게 이동한다는 것이므로 전체 둘레에서 카운트를 빼준 값이 최단거리이고, 절반이 안 된다면 카운트가 최단거리인 것이다.

이 각 지점에 대한 최단거리의 이동값을 결과 변수에 더해 최종적으로 출력하면 되겠다.

결과

맞았습니다!!

모범답안

출처

# empty