[백준/Python] 14620 꽃길

문제

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

 

 

정답코드

# 꽃길
# 복습 횟수:0, 01:00:00, 복습필요O
import sys
from collections import deque
si = sys.stdin.readline
N = int(si())
graph = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(N):
    tmp = list(map(int, si().split()))
    graph.append(tmp)
answer = sys.maxsize

# 완전 탐색
for i in range(1, N-1):
    for j in range(1, N-1):
        visited = [[0 for i in range(N)] for i in range(N)]
        # 첫번째 꽃
        visited[i][j] = 1 # 방문처리
        for idx in range(4):
            ni, nj = i + dx[idx], j + dy[idx]
            visited[ni][nj] = 1 # 방문처리
        
        # 두번째 꽃
        for k in range(1, N-1):
            for l in range(1, N-1):
                q = deque()
                q.append([k, l])
                for idx in range(4):
                    nk, nl = k + dx[idx], l + dy[idx]
                    q.append([nk, nl])
                
                tmp = 0
                for x, y in q:
                    if visited[x][y] == 1:
                        tmp += 1
                if tmp > 0: continue
                
                for x, y in q:
                    visited[x][y] = 1 

                # 세번째 꽃
                for x in range(1, N-1):
                    for y in range(1, N-1):
                        q2 = deque()
                        q2.append([x, y])
                        for idx in range(4):
                            nx, ny = x + dx[idx], y + dy[idx]
                            q2.append([nx, ny])
                        
                        tmp = 0
                        for x, y in q2:
                            if visited[x][y] == 1:
                                tmp += 1
                        if tmp > 0: continue
                        
                        for x, y in q2:
                            visited[x][y] = 1 # 방문처리

                        # 여기까지 코드가 도착하는 경우 겹치지 않는 것임
                        sumi = 0
                        for xx in range(N):
                            for yy in range(N):
                                if visited[xx][yy] == 1:
                                    sumi += graph[xx][yy]
                        
                        answer = min(answer, sumi)

                        for x, y in q2:
                            visited[x][y] = 0 # 원상복구
                # 원상복구
                for x, y in q:
                    visited[x][y] = 0 
print(answer)

 

 

풀이

완전탐색문제이다

for 문이 매우매우 많이 들어가지만 6<=N<=10 이므로 풀 수 있는 문제이다. 

꽃잎이 밖으로 가는 경우 죽는다고 했으므로 범위는 1~ N-2로 잡아 탐색을 한다.

각 단계마다 꽃을 체크해야하므로 첫번째 꽃의 for문 이 끝나는 지점에 두번 째 꽃의 for문이 시작된다.

한 단계를 체크하면 방문한 위치를 초기화 해주어야 하므로 큐에 담고 있다가 for 문이 다음으로 넘어가기 직전에 큐에 담고 있었던 것을 체크해 다시 방문 위치를 초기화해준다.

이과정을 첫번쨰 -> 두번째 -> 세번째 반복하면 문제를 해결할 수 있다.