J1Yun
ZU-TECHLOG
J1Yun
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๐Ÿ“‘ Category (135)
    • Algorithm (61)
      • ๐Ÿ“š Concept (6)
      • ๐Ÿ“˜ Baekjoon Judge (53)
      • ๐Ÿ“— Programmers (2)
    • Computer Science (42)
      • ๐Ÿ”’ Operating System (14)
      • ๐Ÿ“ก Network (15)
      • ๐Ÿ’พ Database (8)
      • ๐Ÿงฉ Design Pattern (4)
      • ๐Ÿ”‘ Security (1)
    • Activities (12)
      • ๐Ÿฆ ๋ฉ‹์Ÿ์ด์‚ฌ์ž์ฒ˜๋Ÿผ 9๊ธฐ (6)
      • ๐Ÿ’ป SW๋งˆ์—์ŠคํŠธ๋กœ 13๊ธฐ (6)
    • Infra (1)
      • โ˜๏ธ AWS (1)
    • Languages (1)
      • ๐Ÿ’™ Python (1)
    • Backend (7)
      • ๐Ÿ”ต Django (4)
      • ๐ŸŸข Node.js (3)
    • Ect. (8)
      • ๐Ÿ’ฌ Talk (0)
      • ๐Ÿ—‚๏ธ ๊ฐœ๋ฐœ์ง๊ตฐ ์ทจ์—… ์ค€๋น„์ž๋ฃŒ (8)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

250x250
hELLO ยท Designed By ์ •์ƒ์šฐ.
J1Yun

ZU-TECHLOG

[BOJ] ๋ฐฑ์ค€ 17144๋ฒˆ ๋ฏธ์„ธ๋จผ์ง€ ์•ˆ๋…•! - ํŒŒ์ด์ฌ(Python)
Algorithm/๐Ÿ“˜ Baekjoon Judge

[BOJ] ๋ฐฑ์ค€ 17144๋ฒˆ ๋ฏธ์„ธ๋จผ์ง€ ์•ˆ๋…•! - ํŒŒ์ด์ฌ(Python)

728x90

๋ฌธ์ œ

๋ฏธ์„ธ๋จผ์ง€๋ฅผ ์ œ๊ฑฐํ•˜๊ธฐ ์œ„ํ•ด ๊ตฌ์‚ฌ๊ณผ๋Š” ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋ฅผ ์„ค์น˜ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ์„ฑ๋Šฅ์„ ํ…Œ์ŠคํŠธํ•˜๊ธฐ ์œ„ํ•ด ๊ตฌ์‚ฌ๊ณผ๋Š” ์ง‘์„ ํฌ๊ธฐ๊ฐ€ R×C์ธ ๊ฒฉ์žํŒ์œผ๋กœ ๋‚˜ํƒ€๋ƒˆ๊ณ , 1×1 ํฌ๊ธฐ์˜ ์นธ์œผ๋กœ ๋‚˜๋ˆด๋‹ค. ๊ตฌ์‚ฌ๊ณผ๋Š” ๋›ฐ์–ด๋‚œ ์ฝ”๋”ฉ ์‹ค๋ ฅ์„ ์ด์šฉํ•ด ๊ฐ ์นธ (r, c)์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์„ ์‹ค์‹œ๊ฐ„์œผ๋กœ ๋ชจ๋‹ˆํ„ฐ๋งํ•˜๋Š” ์‹œ์Šคํ…œ์„ ๊ฐœ๋ฐœํ–ˆ๋‹ค. (r, c)๋Š” rํ–‰ c์—ด์„ ์˜๋ฏธํ•œ๋‹ค.

๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋Š” ํ•ญ์ƒ 1๋ฒˆ ์—ด์— ์„ค์น˜๋˜์–ด ์žˆ๊ณ , ํฌ๊ธฐ๋Š” ๋‘ ํ–‰์„ ์ฐจ์ง€ํ•œ๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์„ค์น˜๋˜์–ด ์žˆ์ง€ ์•Š์€ ์นธ์—๋Š” ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์žˆ๊ณ , (r, c)์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์€ Ar,c์ด๋‹ค.

1์ดˆ ๋™์•ˆ ์•„๋ž˜ ์ ํžŒ ์ผ์ด ์ˆœ์„œ๋Œ€๋กœ ์ผ์–ด๋‚œ๋‹ค.

  1. ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ํ™•์‚ฐ๋œ๋‹ค. ํ™•์‚ฐ์€ ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์žˆ๋Š” ๋ชจ๋“  ์นธ์—์„œ ๋™์‹œ์— ์ผ์–ด๋‚œ๋‹ค.
    • (r, c)์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€๋Š” ์ธ์ ‘ํ•œ ๋„ค ๋ฐฉํ–ฅ์œผ๋กœ ํ™•์‚ฐ๋œ๋‹ค.
    • ์ธ์ ‘ํ•œ ๋ฐฉํ–ฅ์— ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์žˆ๊ฑฐ๋‚˜, ์นธ์ด ์—†์œผ๋ฉด ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ๋Š” ํ™•์‚ฐ์ด ์ผ์–ด๋‚˜์ง€ ์•Š๋Š”๋‹ค.
    • ํ™•์‚ฐ๋˜๋Š” ์–‘์€ Ar,c/5์ด๊ณ  ์†Œ์ˆ˜์ ์€ ๋ฒ„๋ฆฐ๋‹ค.
    • (r, c)์— ๋‚จ์€ ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์€ Ar,c - (Ar,c/5)×(ํ™•์‚ฐ๋œ ๋ฐฉํ–ฅ์˜ ๊ฐœ์ˆ˜) ์ด๋‹ค.
  2. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์ž‘๋™ํ•œ๋‹ค.
    • ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์—์„œ๋Š” ๋ฐ”๋žŒ์ด ๋‚˜์˜จ๋‹ค.
    • ์œ„์ชฝ ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ์€ ๋ฐ˜์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ์ˆœํ™˜ํ•˜๊ณ , ์•„๋ž˜์ชฝ ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ์€ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ์ˆœํ™˜ํ•œ๋‹ค.
    • ๋ฐ”๋žŒ์ด ๋ถˆ๋ฉด ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ๋ฐ”๋žŒ์˜ ๋ฐฉํ–ฅ๋Œ€๋กœ ๋ชจ๋‘ ํ•œ ์นธ์”ฉ ์ด๋™ํ•œ๋‹ค.
    • ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์—์„œ ๋ถ€๋Š” ๋ฐ”๋žŒ์€ ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์—†๋Š” ๋ฐ”๋žŒ์ด๊ณ , ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋กœ ๋“ค์–ด๊ฐ„ ๋ฏธ์„ธ๋จผ์ง€๋Š” ๋ชจ๋‘ ์ •ํ™”๋œ๋‹ค.

๋‹ค์Œ์€ ํ™•์‚ฐ์˜ ์˜ˆ์‹œ์ด๋‹ค.

์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ์— ์นธ์ด ์—†๊ธฐ ๋•Œ๋ฌธ์—, ๋‘ ๋ฐฉํ–ฅ์œผ๋กœ๋งŒ ํ™•์‚ฐ์ด ์ผ์–ด๋‚ฌ๋‹ค.

์ธ์ ‘ํ•œ ๋„ค ๋ฐฉํ–ฅ์œผ๋กœ ๋ชจ๋‘ ํ™•์‚ฐ์ด ์ผ์–ด๋‚œ๋‹ค.

๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์žˆ๋Š” ์นธ์œผ๋กœ๋Š” ํ™•์‚ฐ์ด ์ผ์–ด๋‚˜์ง€ ์•Š๋Š”๋‹ค.

๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉํ–ฅ์œผ๋กœ ์ˆœํ™˜ํ•œ๋‹ค.

๋ฐฉ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, T์ดˆ๊ฐ€ ์ง€๋‚œ ํ›„ ๊ตฌ์‚ฌ๊ณผ์˜ ๋ฐฉ์— ๋‚จ์•„์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์„ ๊ตฌํ•ด๋ณด์ž.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๋‘˜์งธ ์ค„๋ถ€ํ„ฐ R๊ฐœ์˜ ์ค„์— Ar,c (-1 ≤ Ar,c ≤ 1,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์„ค์น˜๋œ ๊ณณ์€ Ar,c๊ฐ€ -1์ด๊ณ , ๋‚˜๋จธ์ง€ ๊ฐ’์€ ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์ด๋‹ค. -1์€ 2๋ฒˆ ์œ„์•„๋ž˜๋กœ ๋ถ™์–ด์ ธ ์žˆ๊ณ , ๊ฐ€์žฅ ์œ— ํ–‰, ์•„๋žซ ํ–‰๊ณผ ๋‘ ์นธ์ด์ƒ ๋–จ์–ด์ ธ ์žˆ๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— T์ดˆ๊ฐ€ ์ง€๋‚œ ํ›„ ๊ตฌ์‚ฌ๊ณผ ๋ฐฉ์— ๋‚จ์•„์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

https://www.acmicpc.net/problem/17144

 

17144๋ฒˆ: ๋ฏธ์„ธ๋จผ์ง€ ์•ˆ๋…•!

๋ฏธ์„ธ๋จผ์ง€๋ฅผ ์ œ๊ฑฐํ•˜๊ธฐ ์œ„ํ•ด ๊ตฌ์‚ฌ๊ณผ๋Š” ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋ฅผ ์„ค์น˜ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ์„ฑ๋Šฅ์„ ํ…Œ์ŠคํŠธํ•˜๊ธฐ ์œ„ํ•ด ๊ตฌ์‚ฌ๊ณผ๋Š” ์ง‘์„ ํฌ๊ธฐ๊ฐ€ R×C์ธ ๊ฒฉ์žํŒ์œผ๋กœ ๋‚˜ํƒ€๋ƒˆ๊ณ , 1×1 ํฌ๊ธฐ์˜ ์นธ์œผ๋กœ ๋‚˜๋ˆด๋‹ค. ๊ตฌ์‚ฌ

www.acmicpc.net

 

๐Ÿ’ก ํ’€์ด ๋ฐ ์ฝ”๋“œ

from copy import deepcopy
r, c, t = map(int, input().split())
graph = []
for _ in range(r):
    graph.append(list(map(int, input().split())))

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

def spread():
    data = deepcopy(graph)
    for x in range(r):
        for y in range(c):
            if graph[x][y] > 0:
                temp, count = graph[x][y] // 5, 0
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if nx < 0 or nx >= r or ny < 0 or ny >= c or graph[nx][ny] == -1:
                        continue
                    data[nx][ny] += temp
                    count += 1
                data[x][y] -= temp * count
    return data

def move(x1, x2):
    data = deepcopy(graph)
    for i in range(1, c-1):
        data[x1][i+1] = graph[x1][i]
        data[x2][i+1] = graph[x2][i]
    for i in range(c-1):
        data[0][i] = graph[0][i+1]
        data[r-1][i] = graph[r-1][i+1]
    for i in range(x1):
        data[i+1][0] = graph[i][0]
        data[i][c-1] = graph[i+1][c-1]
    for i in range(x2+1, r):
        data[i-1][0] = graph[i][0]
        data[i][c-1] = graph[i-1][c-1]
    data[x1][0], data[x2][0], data[x1][1], data[x2][1] = -1, -1, 0, 0
    return data

cleaner = []
for _ in range(t):
    graph = spread()
    for i in range(r):
            if graph[i][0] == -1:
                cleaner.append(i)
    graph = move(cleaner[0], cleaner[1])

result = 0
for i in range(r):
    for j in range(c):
        if graph[i][j] > 0:
            result += graph[i][j]

print(result)

์ฃผ์–ด์ง„ ์กฐ๊ฑด ๊ทธ๋Œ€๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ฃผ์˜ํ•  ์ ์€ ๋ฏธ์„ธ๋จผ์ง€ ํ™•์‚ฐ๊ณผ ๊ณต๊ธฐ์ฒญ์ •๊ธฐ ์ž‘๋™ ์‹œ ์ž…๋ ฅ ๋ฐ›์€ ๋ฏธ์„ธ๋จผ์ง€ ๋ฐ์ดํ„ฐ์— ์ง์ ‘ ๋ณ€ํ˜•์‹œํ‚ค๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ, deepcopy๋กœ ๋ณต์‚ฌ๋ณธ์„ ๋งŒ๋“ค์–ด์„œ ์ ์šฉํ•œ ํ›„ ๋ฎ์–ด ์“ฐ๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ•ด์•ผ ํ•œ๋‹ค. ํ™•์‚ฐ๋˜๊ฑฐ๋‚˜ ์ด๋™ํ•œ ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ๋‹ค๋ฅธ ๊ฒฉ์ž์˜ ๋ฏธ์„ธ๋จผ์ง€ ํ™•์‚ฐ์ด๋‚˜ ์ด๋™์— ์˜ํ–ฅ์„ ๋ผ์น˜๋ฉด ์•ˆ๋˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

728x90

'Algorithm > ๐Ÿ“˜ Baekjoon Judge' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[BOJ] ๋ฐฑ์ค€ 21609๋ฒˆ ์ƒ์–ด ์ค‘ํ•™๊ต - ํŒŒ์ด์ฌ(Python)  (1) 2022.10.07
[BOJ] ๋ฐฑ์ค€ 21608๋ฒˆ ์ƒ์–ด ์ดˆ๋“ฑํ•™๊ต - ํŒŒ์ด์ฌ(Python)  (0) 2022.10.07
[BOJ] ๋ฐฑ์ค€ 15685๋ฒˆ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ - ํŒŒ์ด์ฌ(Python)  (0) 2022.08.23
[BOJ] ๋ฐฑ์ค€ 2133๋ฒˆ ํƒ€์ผ ์ฑ„์šฐ๊ธฐ - ํŒŒ์ด์ฌ(Python)  (0) 2022.08.18
[BOJ] ๋ฐฑ์ค€ 2294๋ฒˆ ๋™์ „ 2 - ํŒŒ์ด์ฌ(Python)  (0) 2022.08.18
    'Algorithm/๐Ÿ“˜ Baekjoon Judge' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€์ด๋‹ค
    • [BOJ] ๋ฐฑ์ค€ 21609๋ฒˆ ์ƒ์–ด ์ค‘ํ•™๊ต - ํŒŒ์ด์ฌ(Python)
    • [BOJ] ๋ฐฑ์ค€ 21608๋ฒˆ ์ƒ์–ด ์ดˆ๋“ฑํ•™๊ต - ํŒŒ์ด์ฌ(Python)
    • [BOJ] ๋ฐฑ์ค€ 15685๋ฒˆ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ - ํŒŒ์ด์ฌ(Python)
    • [BOJ] ๋ฐฑ์ค€ 2133๋ฒˆ ํƒ€์ผ ์ฑ„์šฐ๊ธฐ - ํŒŒ์ด์ฌ(Python)
    J1Yun
    J1Yun
    ๊ฐœ๋ฐœ ๊ด€๋ จ ๊ธฐ์ˆ  ๋ฐ ๊ณต๋ถ€ ๋‚ด์šฉ ๊ธฐ๋ก์žฅ

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”