[BOJ]백준 22939번: 쿠키크루(Python)/BruteForce

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

22939번: 쿠키크루

단어가 안 읽혀서 재밌는 문ㄴ제 ㅎㅎ

최단거리하면 자동으로 BFS와 연관짓게 되는데, 그러한 부분을 역으로 주의해야 한다

이 문제에서는 장애물도 없고, 이동하는 데에 아무런 제약이 없기 때문에 거리를 단순히 맨해튼 거리로 구해주면 시간복잡도가 O(1)로 간단하다

따라서 모든 지원분야에 대해, 모든 정점 방문 가능 순서에 대해 전부 구해주면 되기 때문에 브루트 포스 ~~

import sys
from itertools import permutations

sys.stdin = open('python/input.txt', 'r')
input = sys.stdin.readline

n = int(input())
board = []
home = [0, 0]
cookie = [0, 0]
kinds = ['J', 'C', 'B', 'W']
field = ['Assassin', 'Healer', 'Mage', 'Tanker']
topping = [[] for _ in range(4)]


def dist(a, b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])


for i in range(n):
    board.append(input())
    for j in range(n):
        if board[i][j] == 'H':
            home = [i, j]
        if board[i][j] == '#':
            cookie = [i, j]
        for k in range(4):
            if board[i][j] == kinds[k]:
                topping[k].append([i, j])

    minVal = 10**10
    ans = ''
    for k in range(4):
        perm = permutations(topping[k], 3)
        for p in perm:
            d = dist(home, p[0])+dist(p[0], p[1]) + \
                dist(p[1], p[2])+dist(p[2], cookie)
            if d < minVal:
                minVal = d
                ans = field[k]

print(ans)

우왕 오늘 세 문제 풀엇다 ~~