[백준/python] 22939번 쿠킹크루

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

 

문제

밀가루반죽으로 잘 구워진 킴쿠키는 광활하고 평평한 들판 위에 세워진 쿠키나라의 시민이다. 킴쿠키는 케이크나라의 침략으로 어려워진 쿠키나라를 지키기 위해 할 수 있는 일이 없을까 늘 고민하는 쿠키였다. 그러던 어느날, 고민을 하면서 산책을 하던 킴쿠키는 쿠키나라의 기사단인 쿠키크루를 모집한다는 전단지를 발견하였다. 쿠키크루에 지원하기 위해서는 지원 분야에 맞는 토핑 3개를 몸에 두르고 있어야 한다. 쿠키크루의 지원 분야와 어울리는 토핑은 다음과 같다.

• 침투단(Assassin) - 젤리(J)
• 치유단(Healer) - 초콜릿(C)
• 마법단(Mage) - 베리(B)
• 방어단(Tanker) - 호두(W)

킴쿠키는 쿠키크루에 가입하기로 마음을 먹었지만 쿠키크루의 경쟁률이 높기 때문에 최대한 빠르게 지원을 해야한다. 킴쿠키는 서둘러 집으로 돌아가 N × N 크기의 2차원인 토핑토핑지도를 꺼내 각 토핑들의 위치를 확인하였다. 지도에는 호두, 초콜릿, 베리, 젤리 토핑들의 위치가 각각 3개씩 표시되어 있고 집(H)의 위치, 그리고 쿠키크루에 지원하는 장소인 쿠키크루삥뽕(#)이 표시되어있다. 킴쿠키는 지도를 보고 토핑이 떨어져 있는 위치를 확인한 다음, 같은 종류의 토핑 3개를 몸에 두르고 쿠키크루삥뽕에 가야한다.

최대한 빠르게 쿠키크루에 지원하고 싶어하는 킴쿠키를 위해서, 지도를 보고 우리가 킴쿠키에게 지원해야하는 분야를 알려주자.

킴쿠키는 지도상에서 상, 하, 좌, 우로 움직일 수 있으며 한번에 한 칸 움직일 수 있고 같은 곳을 여러 번 들를 수 있다.

쿠키크루삥뽕에 도착했을 때, 지원하려는 분야 이외의 토핑이 몸에 추가로 둘러져 있어도 상관없으며 아직 지원을 할 수 없는 상황에서도 쿠키크루삥뽕을 거쳐 다른 곳으로 이동할 수 있다.

입력

입력의 첫 번째 줄에는 토핑토핑지도의 크기 N이 주어진다. (4 ≤ N ≤ 100)

입력의 두 번째 줄부터 N개의 줄에 N칸에 걸쳐 토핑토핑지도가 주어진다. 지도에서 X은 빈 땅, H는 집, W, C, B, J는 각각 호두, 초콜릿, 베리, 젤리 토핑이며 #은 쿠키크루에 지원하는 장소인 쿠키크루삥뽕이다.

지도에는 각 토핑들이 3개씩 있고 집과 쿠키크루삥뽕이 하나씩 있음이 보장된다.

출력

킴쿠키가 지원해야하는 분야를 출력한다.

침투단에 지원해야 하면 "Assassin", 치유단이면 "Healer", 마법단이면 "Mage", 방어단이면 "Tanker"를 출력한다.

지원할 수 있는 분야가 여러개라면 침투단, 치유단, 마법단, 방어단 순서로 우선순위를 둔다.

예제 입력 1 복사

10
HXXJXXXXXB
JXXXXXWXXX
XXWXXXXBXX
CXXXXXXXXX
XXXXXXXXXX
XXCXXBXXXX
XXXXXWXXXJ
XXXXXXXXXX
XXXXCXXXXX
XXXXXXXXX#

예제 출력 1 복사

Healer

 

---

풀이

이 문제를 보고 전혀 .. 감이 오지 않아 결국 다른 사람의 코드를 참고하여 풀었다.

 

알고리즘

1. 한줄씩 입력받으며 각각 토핑 종류의 위치값을 저장한다. (H와 #의 위치값도 따로 저장)
토핑은 한 종류당 3개씩 있기 때문에 위치값은 한 토핑당 3개씩 존재할 것임

2. 주어진 토핑의 위치값을 가지고 만들 수 있는 조합을 모두 만들어 본다.
각 토핑 당 위치값이 3개이고, 그 위치들 중 어떤 순서로 갈 수 있는지 모두 저장한다.
(한 종류당 이동할 수 있는 경우의 수가 3! = 6개씩 나올 거임 - 한종류당 토핑이 3개씩 있으니까)

3. 그 방법의 수 중 가장 짧은 거리를 구하고, 그때의 토핑 종류가 곧 답이 된다.
방해물이 없으므로 맨해튼 거리로 짧은 거리를 구할 수 있다.
* 맨해튼 거리: 맨허튼 거리가 (p1,p2) 와(q1,q2) 사이면 맨허튼 거리 = ∣p1−q1∣+∣p2−q2∣ 이다.

 

 

step 1.

J,C,B,W의 위치값을 저장한다. (H,#의 위치도 저장)

ex)

home = [0,0] -> (H)cookie = [9,9] -> (#)

[ [[0, 3], [1, 0], [6, 9]], -> J

[[3, 0], [5, 2], [8, 4]], -> C

[[0, 9], [2, 7], [5, 5]], -> B

[[1, 6], [2, 2], [6, 5]] ] -> W

for i in range(n):
    field[i] = input().strip()
    for j in range(n):
        if field[i][j]=="H":
            home = [i,j]
        if field[i][j]=="#":
            cookie = [i,j]
        for k in range(4):
            if field[i][j]==toppingKinds[k]:
                topping[k].append([i,j])

 

 

step 2.

주어진 토핑의 위치값을 가지고 만들 수 있는 조합을 모두 만들어 본다.

ex) J의 위치값을 가지고 이동할 수 있는 경우의 수

[ ([0, 3], [1, 0], [6, 9]),

([0, 3], [6, 9], [1, 0]),

([1, 0], [0, 3], [6, 9]),

([1, 0], [6, 9], [0, 3]),

([6, 9], [0, 3], [1, 0]),

([6, 9], [1, 0], [0, 3])]

for k in range(4):
    perm = permutations(topping[k],3)	
    # 모두 동일하게 3개의 위치값을 가지고 있으므로, 
    # 모든 위치값을 가지고 이동할 수 있는 경우의 수를 모두 구해서 저장

* 여기서 permutations는 조합을 만들어주는 함수 : permutations(a,b) a에서 b개를 골라 조합을 만들어라

 

step 3.

그 경우의 수 중 가장 짧은 거리를 구하고, 그때의 토핑 종류가 곧 답이 된다.

거리 = (home~0번 토핑 위치) + (0번 토핑  위치~1번 토핑  위치) + (1번 토핑  위치~2번 토핑  위치) +(2번 토핑  위치~cookie)

if문으로 비교하며 가장 짧은 거리 저장, 그때의 토핑 종류 저장

crew = ['Assassin','Healer','Mage','Tanker']

def dist(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])
    
min = 10000
type = 0
for p in perm:
        d = dist(home,p[0])+dist(p[0],p[1])\
            +dist(p[1],p[2])+dist(p[2],cookie)
        if min>d:
            min = d
            type = k
       
print(crew[type])

 

 

정답

import sys
from itertools import permutations
input = sys.stdin.readline

n = int(input())
field = [[] for _ in range(n)]
crew = ['Assassin','Healer','Mage','Tanker']
toppingKinds= ['J','C','B','W']
home = [0,0]
cookie = [0,0]
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):
    field[i] = input().strip()
    for j in range(n):
        if field[i][j]=="H":
            home = [i,j]
        if field[i][j]=="#":
            cookie = [i,j]
        for k in range(4):
            if field[i][j]==toppingKinds[k]:
                topping[k].append([i,j])
min = 10000
type = 0
for k in range(4):
    perm = permutations(topping[k],3)
    print(list(perm))
    for p in perm:
        d = dist(home,p[0])+dist(p[0],p[1])\
            +dist(p[1],p[2])+dist(p[2],cookie)
        if min>d:
            min = d
            type = k

        
print(crew[type])

 

 

시간 복잡도

이렇게 일일이 다 해보는 것에 대해서, 과연 시간 안에 들어올 것인지 궁금했다.

시간복잡도 계산은 처음이라,, 하나씩 계산해봤다.

가장 오래걸리는 코드를 기준으로 계산해 보면, 아래와 같을 것이다.

 

결국 최고의 시간 복잡도는 O(N^2)이 될 것이다.

 

최악의 경우 n이 100이 들어왔다 가정하면 약 10000번 * 상수번 실행한다.

시간 제한이 1초(약 100,000,000번 연산 가능하다고 가정)이기 때문에 아주 널널하게 해결할 수 있었다.