๐ ์นํจ ๋ฐฐ๋ฌ
๋ฐฑ์ค Class4 Gold5
solved_ac[Class4] ์นํจ ๋ฐฐ๋ฌ
๋ฌธ์
ํฌ๊ธฐ๊ฐ NรN์ธ ๋์๊ฐ ์๋ค. ๋์๋ 1ร1ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๋์์ ๊ฐ ์นธ์ ๋น ์นธ, ์นํจ์ง, ์ง ์ค ํ๋์ด๋ค. ๋์์ ์นธ์ (r, c)์ ๊ฐ์ ํํ๋ก ๋ํ๋ด๊ณ , rํ c์ด ๋๋ ์์์๋ถํฐ r๋ฒ์งธ ์นธ, ์ผ์ชฝ์์๋ถํฐ c๋ฒ์งธ ์นธ์ ์๋ฏธํ๋ค. r๊ณผ c๋ 1๋ถํฐ ์์ํ๋ค.
์ด ๋์์ ์ฌ๋ ์ฌ๋๋ค์ ์นํจ์ ๋งค์ฐ ์ข์ํ๋ค. ๋ฐ๋ผ์, ์ฌ๋๋ค์ โ์นํจ ๊ฑฐ๋ฆฌโ๋ผ๋ ๋ง์ ์ฃผ๋ก ์ฌ์ฉํ๋ค. ์นํจ ๊ฑฐ๋ฆฌ๋ ์ง๊ณผ ๊ฐ์ฅ ๊ฐ๊น์ด ์นํจ์ง ์ฌ์ด์ ๊ฑฐ๋ฆฌ์ด๋ค. ์ฆ, ์นํจ ๊ฑฐ๋ฆฌ๋ ์ง์ ๊ธฐ์ค์ผ๋ก ์ ํด์ง๋ฉฐ, ๊ฐ๊ฐ์ ์ง์ ์นํจ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ๋์์ ์นํจ ๊ฑฐ๋ฆฌ๋ ๋ชจ๋ ์ง์ ์นํจ ๊ฑฐ๋ฆฌ์ ํฉ์ด๋ค.
์์์ ๋ ์นธ (r1, c1)๊ณผ (r2, c2) ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ | r1-r2 | + | c1-c2 | ๋ก ๊ตฌํ๋ค. |
์๋ฅผ ๋ค์ด, ์๋์ ๊ฐ์ ์ง๋๋ฅผ ๊ฐ๋ ๋์๋ฅผ ์ดํด๋ณด์.
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
0์ ๋น ์นธ, 1์ ์ง, 2๋ ์นํจ์ง์ด๋ค.
(2, 1)์ ์๋ ์ง๊ณผ (1, 2)์ ์๋ ์นํจ์ง๊ณผ์ ๊ฑฐ๋ฆฌ๋ |2-1| + |1-2| = 2, (5, 5)์ ์๋ ์นํจ์ง๊ณผ์ ๊ฑฐ๋ฆฌ๋ |2-5| + |1-5| = 7์ด๋ค. ๋ฐ๋ผ์, (2, 1)์ ์๋ ์ง์ ์นํจ ๊ฑฐ๋ฆฌ๋ 2์ด๋ค.
(5, 4)์ ์๋ ์ง๊ณผ (1, 2)์ ์๋ ์นํจ์ง๊ณผ์ ๊ฑฐ๋ฆฌ๋ | 5-1 | + | 4-2 | = 6, (5, 5)์ ์๋ ์นํจ์ง๊ณผ์ ๊ฑฐ๋ฆฌ๋ | 5-5 | + | 4-5 | = 1์ด๋ค. ๋ฐ๋ผ์, (5, 4)์ ์๋ ์ง์ ์นํจ ๊ฑฐ๋ฆฌ๋ 1์ด๋ค. |
์ด ๋์์ ์๋ ์นํจ์ง์ ๋ชจ๋ ๊ฐ์ ํ๋์ฐจ์ด์ฆ์ด๋ค. ํ๋ ์ฐจ์ด์ฆ ๋ณธ์ฌ์์๋ ์์ต์ ์ฆ๊ฐ์ํค๊ธฐ ์ํด ์ผ๋ถ ์นํจ์ง์ ํ์ ์ํค๋ ค๊ณ ํ๋ค. ์ค๋ ์ฐ๊ตฌ ๋์ ์ด ๋์์์ ๊ฐ์ฅ ์์ต์ ๋ง์ด ๋ผ ์ ์๋ ์นํจ์ง์ ๊ฐ์๋ ์ต๋ M๊ฐ๋ผ๋ ์ฌ์ค์ ์์๋ด์๋ค.
๋์์ ์๋ ์นํจ์ง ์ค์์ ์ต๋ M๊ฐ๋ฅผ ๊ณ ๋ฅด๊ณ , ๋๋จธ์ง ์นํจ์ง์ ๋ชจ๋ ํ์ ์์ผ์ผ ํ๋ค. ์ด๋ป๊ฒ ๊ณ ๋ฅด๋ฉด, ๋์์ ์นํจ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์๊ฒ ๋ ์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N(2 โค N โค 50)๊ณผ M(1 โค M โค 13)์ด ์ฃผ์ด์ง๋ค.
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๋์์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค.
๋์์ ์ ๋ณด๋ 0, 1, 2๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , 0์ ๋น ์นธ, 1์ ์ง, 2๋ ์นํจ์ง์ ์๋ฏธํ๋ค. ์ง์ ๊ฐ์๋ 2N๊ฐ๋ฅผ ๋์ง ์์ผ๋ฉฐ, ์ ์ด๋ 1๊ฐ๋ ์กด์ฌํ๋ค. ์นํจ์ง์ ๊ฐ์๋ M๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 13๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํ์ ์ํค์ง ์์ ์นํจ์ง์ ์ต๋ M๊ฐ๋ฅผ ๊ณจ๋์ ๋, ๋์์ ์นํจ ๊ฑฐ๋ฆฌ์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2
์์ ์ถ๋ ฅ 1
5
์์ ์ ๋ ฅ 2
5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2
์์ ์ถ๋ ฅ 2
10
์์ ์ ๋ ฅ 3
5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
์์ ์ถ๋ ฅ 3
11
์์ ์ ๋ ฅ 4
5 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
์์ ์ถ๋ ฅ 4
32
๐ ์๊ณ ๋ฆฌ์ฆ
TRY 1 (ํ๋ก์ด๋ ์์ฌ)
์ด ๋ฌธ์ ๋ฅผ ๊ทธ๋ํ ํ์ ๋ฌธ์ ๋ผ๊ณ ์ค์ธํ์ฌ ์ ๊ทผํ๋ค.
Value๊ฐ 1์ธ ๋ชจ๋ ๋ ธ๋์์ 2์ธ ๋ชจ๋ ๋ ธ๋๋ก ๊ฐ๋ ์ต์๋น์ฉ์ ๊ตฌํ ํ ๊ทธ ์ต์๋น์ฉ๋ค ์ค์์์ ์ต์๋ฅผ ํ ๋ฒ ๋ ๊ฑธ๋ฌ์ฃผ๋ฉด ๋๋ค๊ณ ์๊ฐํ๋ค.
์นํจ์ง M๊ฐ๋ฅผ ์ ํํ๋ค๋ ์กฐ๊ฑด์ For๋ฌธ์ ํตํ์ฌ ๋จ์ ๊ตฌํํ๋ฉด ๋๋ค๊ณ ์๊ฐํ์ง๋ง ์ด๋ ๋ด๊ฐ ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ ๋ชป ์๊ณ ์์ด์ ๋ฐ์ํ ์ฐฉ๊ฐ์ด๋ค.
[ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ Weight๊ฐ ์๋ ๊ทธ๋ํ์์ ๋ชจ๋ ๋ ธ๋์์ ๋ชจ๋ ๋ ธ๋๋ก ๊ฐ๋ ์ต์ ๋น์ฉ์ ๊ตฌํ ๋ ์ฌ์ฉํ๋ค.]
๊ทธ๋ฐ๋ฐ ์ด ๋ฌธ์ ์์๋ Weight๊ฐ ์๋ค. ๋ฐ๋ผ์ ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ ๊ฒ์ ์ ์ ์น ์๋ค.
TRY 2 (๋ฐฑํธ๋ํน)
๊ฒฐ๊ตญ โ์๊ณ ๋ฆฌ์ฆ ๋ถ๋ฅโ ํํธ๋ฅผ ์ฐธ๊ณ ํ์๋๋ฐ ๋ฌธ์ ๊ฐ ๋ฐฑํธ๋ํน์ผ๋ก ๋ถ๋ฅ๋์ด ์์๋ค.
[๋ฐฑํธ๋ํน์ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ธํด์ผํ ๋ & ๋ฐ๋ณต๋ฌธ์ผ๋ก ํ์ธ ๋ถ๊ฐํ ๊ฒฝ์ฐ ์ฌ์ฉํ๋ค.]
์ด๋ฅผ ๋ณธ ๋ฌธ์ ์ ์ ์ฉ์์ผ๋ณด๋ฉด ์นํจ์ง M๊ฐ๋ฅผ ์ ํํ๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ธํด์ผ ํ๊ณ ๊ทธ M๊ฐ๊ฐ ๋ฏธ์ง์์ด๋ฏ๋ก For๋ฌธ์ ์ฌ์ฉํ์ฌ ์ค๊ณ๋ฅผ ํ์ง ๋ชป ํ๋ค. ๋ฐ๋ผ์ ์ด ๋ฌธ์ ๋ ๋ฐฑํธ๋ํน์ผ๋ก ํ ์ ์๋ ๋ฌธ์ ์ด๋ค.
๊ทธ๋ฐ๋ฐ ์ด ๋ํ ๋ฐฑํธ๋ํน์ผ๋ก ๊ตฌํํ๊ธฐ๊ฐ ๊น๋ค๋ก์ ๋ค. ๊ทธ๋์ ๊ฒฐ๊ตญ ์๋ฃจ์ ์ ์ฐธ๊ณ ํ๋ ค๊ณ ํ์์ผ๋ ๋๋ถ๋ถ์ ์ฌ๋๋ค์ด ๋ฐฑํธ๋ํน์ ์ฌ์ฉํ์ฌ ํ์ง ์๊ณ ์์ ํ์ ์ ๊ทผ๋ฒ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ์๋ค.
์ ๋ธ๋ฃจํธ ํฌ์ค๋ฅผ ์ฌ์ฉํ ๊น?
TRY 3 (๋ธ๋ฃจํธ ํฌ์ค)
[๋ธ๋ฃจํธ ํฌ์ค๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ธํด์ผํ ๋ ์ฌ์ฉํ๋ค.]
๋ฐฑํธ๋ํน๊ณผ ์ฐจ์ด์ ์ โ๋ฐ๋ณต๋ฌธ์ผ๋ก ํ์ธ ๋ถ๊ฐํ ๊ฒฝ์ฐโ๋ผ๋ ์กฐ๊ฑด์ด ๋น ์ก๋ค. ์ด ๋ฌธ์ ๋ฅผ ๋ค์ ๊ณ ์ฐฐํด ๋ณด์์ ๋, ์ด ๋ฌธ์ ๋ ๋ฐ๋ณต๋ฌธ์ผ๋ก ํ์ธ์ด ๊ฐ๋ฅํ๋ค.
๋ฐ๋ก โ์กฐํฉโ์ ์ด์ฉํ๋ฉด M๊ฐ์ ๋ฏธ์ง์๋งํผ ๋ฐ๋ณต๋ฌธ์ ๋๋ ค์ค ์ ์๋ค.
๋ฐ๋ผ์ ๋ฐฑํธ๋ํน๋ณด๋ค๋ ์กฐํฉ์ ์ด์ฉํ ์์ ํ์ ๊ธฐ๋ฒ์ผ๋ก ํธ๋ ๊ฒ์ด ์กฐ๊ธ ๋ ๋ง๋ ํ์ด๊ฐ ์๋๊น ์๊ฐํด๋ณธ๋ค.
๐ ์ค๊ณ
- ์นํจ M๊ฐ๋ฅผ ์ ํํ๋ค.(์กฐํฉ)
- ๋ชจ๋ ์ง๊ณผ
- ๋ชจ๋ ์ ํํ ์นํจ์ ์ํํ๋ฉฐ
- ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ค. = ์นํจ ๊ฑฐ๋ฆฌ
- ๋์ ์นํจ ๊ฑฐ๋ฆฌ๋ฅผ โ์นํจ ๊ฑฐ๋ฆฌโ๋งํผ ์ฆ๊ฐ์ํจ๋ค.
- ๋ชจ๋ ์ ํํ ์นํจ์ ์ํํ๋ฉฐ
- ์ต์ ๋์ ์นํจ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์ ์ํจ๋ค.
- ๋ชจ๋ ์ง๊ณผ
๐จ๐ปโ๐ป CODE
import sys
input = sys.stdin.readline
from itertools import combinations
INF = int(1e9)
N, M = map(int,input().split())
house = []
chicken = []
for i in range(N):
temp = list(map(int,input().split()))
for j in range(N):
if temp[j] == 1:
house.append((i,j))
if temp[j] == 2:
chicken.append((i,j))
answer = INF
for c in combinations(chicken,M):
city_distance = 0
for h in house:
chicken_distance = INF
for i in range(M):
chicken_distance = min(chicken_distance,abs(c[i][0]-h[0])+abs(c[i][1]-h[1]))
city_distance += chicken_distance
answer = min(answer,city_distance)
print(answer)