[BOJ] 14620 - 꽃길

사용 언어: Python3

문제

백준 14620

코드

내 풀이

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

dx, dy = [0,-1,0,1], [1,0,-1,0]
flower = {} # 씨앗 당 5평 가격
ck = [[False for _ in range(N)] for _ in range(N)] # 특정 위치에 꽃이 심어져있는지 체크하기 위한 리스트

# flower init (씨앗 당 5평 가격)
for i in range(1, N-1):
  for j in range(1, N-1):
    price = garden[i][j] # 씨앗
    for zx,zy in zip(dx,dy):
      price += garden[i+zx][j+zy] # 네 꽃잎
    flower[(i,j)] = price # dict update

# dictionary sort
flower = dict(sorted(flower.items(), key=lambda x:x[1])) # x[0]:key 기준, x[1]:value 기준

ans = 0
cnt = 0 # 세 송이만
for pos, val in flower.items():
  if cnt == 3:
    break
  if ck[pos[0]][pos[1]] == False: # 씨앗 -> 빈 땅이라면
    isLeapEmpty = True
    for zx,zy in zip(dx,dy):
      if ck[pos[0]+zx][pos[1]+zy] != False: # 네 꽃잎 빈 땅이 아니라면
        isLeapEmpty = False
    if isLeapEmpty == True:
      ck[pos[0]][pos[1]] = True # 씨앗 심기
      for zx,zy in zip(dx,dy):
          ck[pos[0]+zx][pos[1]+zy] = True # 네 꽃잎
      ans += val
      cnt += 1
    
print(ans)

• 예제 출력은 동일한데, 제출하면 틀렸다고 나온다..

다른 풀이

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

ans = 10000 # 최대 10000원
dx, dy = [0,0,-1,0,1], [0,1,0,-1,0] # 가만히 있는 것 추가 -> (0,0)

# 꽃이 a,b,c 위치에 있을 때 비용 (가능할 때만 리턴)
def ck(lst): 
  ret = 0 # 비용
  flower = [] # 꽃 위치
  for pos in lst:
    # ✅ 2. 씨앗의 위치를 다시 (x,y)로 변환
    x = pos // N
    y = pos % N
    # 예외 처리
    if x == 0 or x == N-1 or y == 0 or y == N-1:
      return 10000
    for w in range(5): # 가만히, 4방향
      flower.append((x+dx[w], y+dy[w])) # tuple append
      ret += garden[x+dx[w]][y+dy[w]]
  # ✅ 꽃잎이 겹친다면 flower set이 15(=5평*3송이)가 나오지 않는다
  if len(set(flower)) != 15: 
    return 10000
  return ret
    
# 전수조사
# ✅ 1. 씨앗의 위치를 (x,y) => 0부터 (N^2-1)까지의 한 자리 수로 매칭
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])) # 최솟값으로 ans 갱신

print(ans)

• N이 6<=N<=10 범위로 주어졌다.
  • 최대를 생각해보면, N=10일 때 N*N=100이고, 꽃이 세 송이니까 전수조사를 하면 100^3(백만)의 시간 복잡도를 가진다.
  • 🌟 백만 혹은 천만까지는 “전수조사”로 풀면 된다!
• 씨앗의 위치를 (x,y) => 0부터 (N^2-1)까지의 한 자리 수(pos)로 매칭하여 더욱 간단히 풀 수 있었다.
  • 다시 복구할 때는, x=pos//N과 y=pos%N으로 복구할 수 있었다.
• len(set())을 이용해 꽃잎이 겹치는지 검증할 수 있었다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기