PS

[๋ฐฑ์ค€] 1058 ์นœ๊ตฌ with Python

ํ˜•์ค€_It's 2022. 2. 1. 01:48
728x90
๋ฐ˜์‘ํ˜•

๐Ÿ“Œ BOJ 1058 ์นœ๊ตฌ

๐Ÿ’ก ์กฐ๊ฑด

  1. ์–ด๋–ค ์‚ฌ๋žŒ A๊ฐ€ ๋˜๋‹ค๋ฅธ ์‚ฌ๋žŒ B์˜ 2-์นœ๊ตฌ๊ฐ€ ๋˜๊ธฐ ์œ„ํ•ด์„ , ๋‘ ์‚ฌ๋žŒ์ด ์นœ๊ตฌ์ด๊ฑฐ๋‚˜, A์™€ ์นœ๊ตฌ์ด๊ณ , B์™€ ์นœ๊ตฌ์ธ C๊ฐ€ ์กด์žฌํ•ด์•ผ ๋œ๋‹ค.
  2. ์—ฌ๊ธฐ์„œ ๊ฐ€์žฅ ์œ ๋ช…ํ•œ ์‚ฌ๋žŒ์€ 2-์นœ๊ตฌ์˜ ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋งŽ์€ ์‚ฌ๋žŒ์ด๋‹ค. ๊ฐ€์žฅ ์œ ๋ช…ํ•œ ์‚ฌ๋žŒ์˜ 2-์นœ๊ตฌ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.
  3. A์™€ B๊ฐ€ ์นœ๊ตฌ๋ฉด, B์™€ A๋„ ์นœ๊ตฌ์ด๊ณ , A์™€ A๋Š” ์นœ๊ตฌ๊ฐ€ ์•„๋‹ˆ๋‹ค.
  4. ์‚ฌ๋žŒ์˜ ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 50๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค.
    ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๊ฐ ์‚ฌ๋žŒ์ด ์นœ๊ตฌ์ด๋ฉด Y, ์•„๋‹ˆ๋ฉด N์ด ์ฃผ์–ด์ง„๋‹ค.
    ๊ฐ€์žฅ ์œ ๋ช…ํ•œ ์‚ฌ๋žŒ์˜ 2-์นœ๊ตฌ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.
  5. ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์œ ํ˜•์˜ ๋ฌธ์ œ

๐Ÿ–ฅ ์†Œ์Šค ์ฝ”๋“œ

from sys import stdin

n = int(stdin.readline())
arr = []
for i in range(n):
    temp = stdin.readline().rstrip().replace("N", '0').replace("Y", '1')
    data = list(map(int, list(temp)))
    arr.append(data)

res = [0] * n
test = [item[:] for item in arr]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i != j:
                if arr[i][k] and arr[k][j]:
                    test[i][j] = 1

res = 0
for i in range(n):
    friends = sum(test[i])
    if res < friends:
        res = friends

print(res)

๐Ÿ”– ์˜ˆ์ œ ๋ฐ ์‹คํ–‰๊ฒฐ๊ณผ

์˜ˆ์ œ

10
NNNNYNNNNN
NNNNYNYYNN
NNNYYYNNNN
NNYNNNNNNN
YYYNNNNNNY
NNYNNNNNYN
NYNNNNNYNN
NYNNNNYNNN
NNNNNYNNNN
NNNNYNNNNN

์‹คํ–‰๊ฒฐ๊ณผ

8

โŒจ๏ธ ๋ฌธ์ œ ํ’€์ด

  1. ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•œ๋‹ค.
  2. Y๋ฅผ 1๋กœ, N์„ 0์œผ๋กœ ๋ณ€ํ™˜ํ•œ ๋’ค, arr์— ์ž…๋ ฅ๋ฐ›์€ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•œ๋‹ค.
  3. test ๋ฐฐ์—ด์— arr๋ฐฐ์—ด์„ ๋ณต์‚ฌํ•œ ๋’ค, ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋Œ๋ฆฌ๊ธฐ ์œ„ํ•œ 3์ค‘ ๋ฐ˜๋ณต๋ฌธ์„ ์ˆœํšŒํ•œ๋‹ค.
  4. arr[i][k] ์™€ arr[k][j] ๊ฐ€ 1์ด๋ผ๋ฉด, test[i][j]์— 1์„ ์ €์žฅํ•œ๋‹ค.
    i์™€ j ๊ฐ€ ํ•œ๋‹ค๋ฆฌ ๊ฑด๋„ˆ์„œ ์นœ๊ตฌ์ธ์ง€ ํ™•์ธํ•˜๋Š” ๊ตฌ๊ฐ„์ด๋‹ค.
  5. test ๋ฐฐ์—ด์„ ์ˆœํšŒํ•˜๋ฉด์„œ test[i]์˜ ํ•ฉ์ด ์ตœ๋Œ“๊ฐ’์ธ ๊ฒƒ์„ ์ฐพ์•„์„œ ๊ฒฐ๊ณผ๊ฐ’์„ ์ €์žฅํ•  res ๋ณ€์ˆ˜์— ์ €์žฅํ•˜๊ณ , ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ’พ ๋А๋‚€์ 

  1. ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‘์šฉ๋ฌธ์ œ์˜€๋‹ค.
  2. ๋ชจ๋“  ๋…ธ๋“œ์—์„œ์˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๋Š” ๋ฐฉ์‹์ด ์•„๋‹Œ,
    ๋ชจ๋“  ๋…ธ๋“œ์—์„œ ์นœ๊ตฌ๊ฐ€ ๋  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ๋ฅผ ์ฐพ์•„ test ๋ฐฐ์—ด์— ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ํ’€์ดํ–ˆ๋‹ค.
๋ฐ˜์‘ํ˜•