알고리즘 공부/미분류
백준 꽃길 14620번 파이썬
_우지
2022. 2. 9. 13:48
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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
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)
|
cs |
배운점
n = int(stdin.readline())원래 나는 sys.stdin.readline()을 사용하는데 디버깅이 불편한데, 이분처럼 사용하면 디버깅할때 편했다.
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
그리고 set을 사용하신 이 생각이 굉장히 매력적이였다. set은 중복이 허용되지 않기 때문에 나는 dfs가 끝나면 다시 visit을 True => False로 바꾸어 주었는데 set update와 차집합 연산을 사용하는 것이 좋았다.
set(집합)의 update
- dictionary의 update는 여러값을 수정 또는 추가할때 사용하지만만, set은 중복은 자동으로 제거되고 수정이라는 개념보다, 여러데이터를 한번에 추가할 때 사용한다.
>>> k = {1, 2, 3}
>>> k.update([3, 4, 5])
>>> k
{1, 2, 3, 4, 5}global을 이런식으로 ..
왜 저렇게 쓰셨지 했는데, 알고보니 global 변수를 선언하지 않고 저런식으로 리스트에 넣어서 만드신 것이였다. 또 하나 배웠다.
그리고 마지막 45번째줄은 list안에 값을 출력하는 건데. 나라면 그냥 print(res[0])이렇게 출력했을꺼같다.
그리고 6번째줄에 res = int(1e9)인데 정수 최대값이 2147483647 이니까 res = int(3e9)로 넣으면 더 좋지않을까 싶다.
int(1e9) = 1000000000 인 것도 다시한번 배웠다.