๐Ÿ— ์น˜ํ‚จ ๋ฐฐ๋‹ฌ

๋ฐฑ์ค€ 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)

ยฉ 2022. All rights reserved.

Powered by Hydejack v9.1.6