백준 꽃길 14620번 파이썬

import sys
input = sys.stdin.readline

N = int(input())
graph = [list(map(int,input().split())) for _ in range(N)]
visit = [[False]*N for _ in range(N)]

dx = [-1,0,1,0]
dy = [0,1,0,-1]

# 한꽃에 메겨질 수 있는 코스트값이 1000이므로 3개이면 3000
global ans
ans = 3000


def dfs(limit,total):
    # 꽃을 3개 심은경우 cost를 비교해서 더 적은 값이라면 ans에 넣는다.
    if limit == 3 :
        global ans 
        # print(total)
        ans = min(ans,total)
        return 
    # visit[x][y] = True
    
    for i in range(1,N-1):
        for j in range(1,N-1):
            # key 꽃을 심을 수 있는가 없는가 판단여부 
            key = False
            money = 0
            if not visit[i][j] :
                money += graph[i][j]
                for k in range(4):
                    xx = i + dx[k]
                    yy = j + dy[k]
                    if visit[xx][yy] or xx < 0 or yy<0 or xx>=N or yy >= N :
                        break
                    if k == 3 :
                        key = True
                    money += graph[xx][yy]
            # 다 심을 수 있는경우 
            if key :
                # 다섯개의 칸 모두 visit 처리
                visit[i][j]=True
                for k in range(4):
                    xx = i + dx[k]
                    yy = j + dy[k]
                    visit[xx][yy]=True
                # print(f'좌표: {i}, {j}')
                # print(f'money: {total+money}')
                dfs(limit+1,total+money)
                # dfs에서 나왔을때 visit을 다시 False로 변경
                for k in range(4):
                    xx = i + dx[k]
                    yy = j + dy[k]
                    visit[xx][yy]=False
                visit[i][j]=False

dfs(0,0)
print(ans)

풀면서 배운점:

 

map과 같은 변수명인 리스트를 생성해서 map함수가 실행되지않아 당황했다. 어 이게 왜 안되지? 나는 내가 치매에 걸린줄 알았다.

 

 

그리고 기존에는 4-5 째 줄처럼 input을 그래프 배열에 넣었는데, 이제는 7번째처럼 바꿔보려고 한다. 이게 더 깔끔하기때문이다.

 

다른분들 코드 1

 

from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 9)
 
n = int(stdin.readline())
arr = []
res = [int(1e9)]
visited = set()
dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]
 
for _ in range(n):
    arr.append(list(map(int, stdin.readline().split())))
 
 
def solve(cnt, cost, v):
    if cnt == 3:
        res[0] = min(res[0], cost)
 
    else:
        for i in range(1, n - 1):
            for j in range(1, n - 1):
                temp_visit = set()
                temp_visit.add((i, j))
                tf = 1
                temp = arr[i][j]
                for k in range(4):
                    nx, ny = i + dx[k], j + dy[k]
                    if -1 < nx < n and -1 < ny < n:
                        if (nx, ny) not in v:
                            temp += arr[nx][ny]
                            temp_visit.add((nx, ny))
                        else:
                            tf = 0
                            break
                    else:
                        tf = 0
                        break
 
                if tf and temp_visit:
                    v.update(temp_visit)
                    solve(cnt + 1, cost + temp, v)
                    v -= temp_visit
 
 
solve(0, 0, visited)
print(*res)

global을 이런식으로 ..

왜 저렇게 쓰셨지 했는데, 알고보니 global 변수를 선언하지 않고 저런식으로 리스트에 넣어서 만드신 것이였다. 또 하나 배웠다. 

그리고 마지막 45번째줄은 list안에 값을 출력하는 건데. 나라면 그냥 print(res[0])이렇게 출력했을꺼같다.

 

그리고 6번째줄에 res = int(1e9)인데 정수 최대값이 2147483647 이니까 res = int(3e9)로 넣으면 더 좋지않을까 싶다.

int(1e9) = 1000000000 인 것도 다시한번 배웠다.