코테분석#7-2 꽃길(백준 14620)

1. 문제

2. 나의 풀이

3. 쌤's 풀이

• 전수조사와 방향벡터를 이용해서 푸는 문제
• 100만 1000만 이하의 시간복잡도면 전수조사 ok!

N = int(input())
G = [list(map(int, input().split())) for i in range(N)]

# 0*N+0
# 0 ~ N**N -1 까지

ans = 10000
# 정지,위,아래,우,좌
dx, dy = [0,0,0,1,-1],[0,1,-1,0,0]

# 꽃 a,b,c에 대한 비용
def ck(list):
	ret = 0
    flow = []
        
    for flower in list:
    	x = flower // N
        y = flower % N
        if x == 0 or x == N-1 or y == 0 or y == N-1:
    		return 10000
        for w in range(5):
        	flow.append((x+dx[w], y+dy[w]))
            ret += G[x+dx[w]][y+dy[w]]
            
    if len(set(flow)) != 15:
    	return 10000
    return ret

for i in range(N*N):
    for j in range(i+1, N*N):
        for k in range(j+1,N*N):
        	ans = min(ans, ck([i,j,k]))

print(ans)

4. 느낀 점

• 전수조사...!