BOJ 9205 _ 맥주 마시면서 걸어가기 _ 파이썬

📃 문제

BOJ 9205 맥주 마시면서 걸어가기

알고리즘 - 플로이드워셜,DP,DFS

입출력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)
각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).
다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)
송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.

💡 풀이 과정

1) 플로이드 워셜 (DP)

문제 분류상 DFS였는데 도저히 DFS로 풀이 로직이 생각나지 않았다.이차원 배열로 각 지점마다의 거리를 적어보니 플로이드 워셜 방법으로 가능할 것 같았다

플로이드 워셜의 결과인 모든노드→모든노드 의 최단거리를 구하고 나서 집→축제장소의 값을 보면 되니까!

31256KB / 4832ms

import sys
input = sys.stdin.readline
maxi = 1000
t = int(input())
for _ in range(t):
    n = int(input())
    xy= []
    for _ in range(n+2):
        xy.append(list(map(int,input().split())))
    arr = [[int(1e9)] * (n+2) for _ in range(n+2)]
    for i in range(n+2):
        for j in range(i,n+2):
            arr[i][j] = 1 if abs(xy[j][0] - xy[i][0]) + abs(xy[j][1] - xy[i][1])<=1000 else int(1e9)
    dist = [0] * (n+2)
    for k in range(1,n+2):
        for i in range(n+2):
            for j in range(n+2):
                if arr[i][k] <=maxi and arr[k][j] <= maxi:
                    arr[i][j] = min(arr[i][j] , arr[i][k] + arr[k][j])

    print('happy' if arr[0][-1]<int(1e9) else 'sad')

• 주의할 것
  arr 초기화하는 for문이나 DP에서의 for문에서 중간 중간 범위 설정에 오류가 많았다 ..^^ 다익스트라로 시도했다가 바꾸는 과정에서 미처 고치지 못했기 때문이었다 !!!!☹️

2) DFS

맞힌 사람의 시간을 보니 40초대였다 … 이렇게나 빨리 가능하다구? 하고 보니까 DFS였다! DFS는 O(정점 수 + 간선 수) 이지만 플로이드워셜은 O(n^3)이니 그럴만도 !

• 풀이 방법
  dfs 함수의 작업은, 하나의 위치(집,편의점,축제)에 대해 인덱스 값을 인자로 받는다.
  그 위치에 대해 방문처리를 한다.
  1번(첫번째 편의점)위치 부터 축제위치 (즉, 집의 위치를 제외한 나머지 모든 위칠)를 모두 확인하며 맨허튼거리가 1000이하이고 방문하지 않은 위치에 대해 재귀로 dfs를 호출한다.
  dfs 함수 호출 시작은 0번, 즉 집의 인덱스 부터 한다.
  축제위치에 방문 처리가 되었다면 happy 아니면 sad를 출력한다

import sys
input = sys.stdin.readline

t = int(input())

def manhattanD(x,y):
    return abs(x[0] - y[0]) + abs(x[1] - y[1])
def cnvDFS(u):
    visited[u] = 1
    for v in range(1, n+2):
        if manhattanD(xy[u], xy[v]) <= 1000 and not visited[v]:
            cnvDFS(v)

for _ in range(t):
    n = int(input())
    xy = [list(map(int,input().split())) for _ in range(n+2)]
    visited = [0] * (n+2)
    cnvDFS(0)
    if visited[-1]:
        print("happy")
    else:
        print("sad")