๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 14500_ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ

๋ฟŒ์•ผ._. 2022. 5. 31. 21:43

Gold V

๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/14500)

<ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ>

๋ฌธ์ œ 

 

ํด๋ฆฌ์˜ค๋ฏธ๋…ธ๋ž€ ํฌ๊ธฐ๊ฐ€ 1 ×1์ธ ์ •์‚ฌ๊ฐํ˜•์„ ์—ฌ๋Ÿฌ ๊ฐœ ์ด์–ด์„œ ๋ถ™์ธ ๋„ํ˜•์ด๋ฉฐ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•ด์•ผ ํ•œ๋‹ค.

  • ์ •์‚ฌ๊ฐํ˜•์€ ์„œ๋กœ ๊ฒน์น˜๋ฉด ์•ˆ ๋œ๋‹ค.
  • ๋„ํ˜•์€ ๋ชจ๋‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์–ด์•ผ ํ•œ๋‹ค.
  • ์ •์‚ฌ๊ฐํ˜•์˜ ๋ณ€๋ผ๋ฆฌ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์–ด์•ผ ํ•œ๋‹ค. ์ฆ‰, ๊ผญ์ง“์ ๊ณผ ๊ผญ์ง“์ ๋งŒ ๋งž๋‹ฟ์•„ ์žˆ์œผ๋ฉด ์•ˆ ๋œ๋‹ค.

์ •์‚ฌ๊ฐํ˜• 4๊ฐœ๋ฅผ ์ด์–ด ๋ถ™์ธ ํด๋ฆฌ์˜ค๋ฏธ๋…ธ๋Š” ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ๋ผ๊ณ  ํ•˜๋ฉฐ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ 5๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค.

์•„๋ฆ„์ด๋Š” ํฌ๊ธฐ๊ฐ€ N×M์ธ ์ข…์ด ์œ„์— ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ ํ•˜๋‚˜๋ฅผ ๋†“์œผ๋ ค๊ณ  ํ•œ๋‹ค. ์ข…์ด๋Š” 1 ×1 ํฌ๊ธฐ์˜ ์นธ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ์œผ๋ฉฐ, ๊ฐ๊ฐ์˜ ์นธ์—๋Š” ์ •์ˆ˜๊ฐ€ ํ•˜๋‚˜ ์“ฐ์—ฌ ์žˆ๋‹ค.

ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ ํ•˜๋‚˜๋ฅผ ์ ์ ˆํžˆ ๋†“์•„์„œ ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ๊ฐ€ ๋†“์ธ ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๋“ค์˜ ํ•ฉ์„ ์ตœ๋Œ€๋กœ ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ๋Š” ๋ฐ˜๋“œ์‹œ ํ•œ ์ •์‚ฌ๊ฐํ˜•์ด ์ •ํ™•ํžˆ ํ•˜๋‚˜์˜ ์นธ์„ ํฌํ•จํ•˜๋„๋ก ๋†“์•„์•ผ ํ•˜๋ฉฐ, ํšŒ์ „์ด๋‚˜ ๋Œ€์นญ์„ ์‹œ์ผœ๋„ ๋œ๋‹ค.

 

 

์ž…๋ ฅ

 

์ฒซ์งธ ์ค„์— ์ข…์ด์˜ ์„ธ๋กœ ํฌ๊ธฐ N๊ณผ ๊ฐ€๋กœ ํฌ๊ธฐ M์ด ์ฃผ์–ด์ง„๋‹ค. (4 ≤ N, M ≤ 500)
๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์ข…์ด์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. i๋ฒˆ์งธ ์ค„์˜ j๋ฒˆ์งธ ์ˆ˜๋Š” ์œ„์—์„œ๋ถ€ํ„ฐ i๋ฒˆ์งธ ์นธ, ์™ผ์ชฝ์—์„œ๋ถ€ํ„ฐ j๋ฒˆ์งธ ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜์ด๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ์ˆ˜๋Š” 1,000์„ ๋„˜์ง€ ์•Š๋Š” ์ž์—ฐ์ˆ˜์ด๋‹ค.

 

์ถœ๋ ฅ 

 

์ฒซ์งธ ์ค„์— ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ๊ฐ€ ๋†“์ธ ์นธ์— ์“ฐ์ธ ์ˆ˜๋“ค์˜ ํ•ฉ์˜ ์ตœ๋Œ“๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

 

๋ฌธ์ œ ํ’€์ด

 

 - my solution (Python)

import sys

def main():
    n,m=map(int, sys.stdin.readline().split()) # ์„ธ๋กœ, ๊ฐ€๋กœ

    arr=[]
    for i in range(n):
        arr.append(list(map(int,sys.stdin.readline().split())))

    result=0

    Fig_1_x=[0,1,2,3]
    Fig_1_y=[0,0,0,0]

    for i in range(n):
        for j in range(m):
            flag_a=True;flag_b=True;temp_a=0;temp_b=0
            for k in range(4):
                x_1=i+Fig_1_x[k]
                y_1=j+Fig_1_y[k]
                if 0<=x_1<n and 0<=y_1<m:
                    temp_a+=arr[x_1][y_1]
                else:
                    flag_a=False
                x_2=i+Fig_1_y[k]
                y_2=j+Fig_1_x[k]
                if 0<=x_2<n and 0<=y_2<m:
                    temp_b+=arr[x_2][y_2]
                else:
                    flag_b=False
            if flag_a==True and result<temp_a:
                result=temp_a
            if flag_b==True and result<temp_b:
                result=temp_b

    Fig_2_x=[0,0,1,1]
    Fig_2_y=[0,1,0,1]

    for i in range(n):
        for j in range(m):
            temp=0; flag=True
            for k in range(4):
                x=i+Fig_2_x[k]
                y=j+Fig_2_y[k]
                if 0<=x<n and 0<=y<m:
                    temp+=arr[x][y]
                else:
                    flag=False
                    break
            if flag==True and result<temp:
                result=temp

    Fig_3_x=[[0,1,2,2],[0,1,2,2],[0,0,1,2],[0,0,1,2]]
    Fig_3_y=[[0,0,0,1],[0,0,0,-1],[0,-1,-1,-1],[0,1,1,1]]

    for i in range(n):
        for j in range(m):
            for k in range(4):
                cnt_a = 0;cnt_b = 0;temp_a = 0;temp_b = 0
                for v in range(4):
                    x_1=i+Fig_3_x[k][v]
                    y_1=j+Fig_3_y[k][v]
                    if 0<=x_1<n and 0<=y_1<m:
                        cnt_a+=1
                        temp_a+=arr[x_1][y_1]
                    x_2=i+Fig_3_y[k][v]
                    y_2=j+Fig_3_x[k][v]
                    if 0<=x_2<n and 0<=y_2<m:
                        cnt_b+=1
                        temp_b+=arr[x_2][y_2]
                if cnt_a==4 and result<temp_a:
                    result=temp_a
                if cnt_b==4 and result<temp_b:
                    result=temp_b

    
    Fig_4_x=[[0,0,1,0],[0,0,-1,0],[0,0,-1,1],[0,0,-1,1]]
    Fig_4_y=[[0,1,1,2],[0,1,1,2],[0,1,1,1],[0,-1,-1,-1]]

    for i in range(n):
        for j in range(m):
            for k in range(4):
                cnt_a = 0;temp_a = 0
                for v in range(4):
                    x_1=i+Fig_4_x[k][v]
                    y_1=j+Fig_4_y[k][v]
                    if 0<=x_1<n and 0<=y_1<m:
                        cnt_a+=1
                        temp_a+=arr[x_1][y_1]
                if cnt_a==4 and result<temp_a:
                    result=temp_a

    Fig_5_x=[[0,1,1,2],[0,1,1,2]]
    Fig_5_y=[[0,0,1,1],[0,0,-1,-1]]

    for i in range(n):
        for j in range(m):
            for k in range(2):
                cnt_a = 0;cnt_b = 0;temp_a = 0;temp_b = 0
                for v in range(4):
                    x_1=i+Fig_5_x[k][v]
                    y_1=j+Fig_5_y[k][v]
                    if 0<=x_1<n and 0<=y_1<m:
                        cnt_a+=1
                        temp_a+=arr[x_1][y_1]
                    x_2=i+Fig_5_y[k][v]
                    y_2=j+Fig_5_x[k][v]
                    if 0<=x_2<n and 0<=y_2<m:
                        cnt_b+=1
                        temp_b+=arr[x_2][y_2]
                if cnt_a==4 and result<temp_a:
                    result=temp_a
                if cnt_b==4 and result<temp_b:
                    result=temp_b
    print(result)

if __name__=='__main__':
    main()

 

Fig_1_x, Fig_1_y

 = ํšŒ์ „, ๋Œ€์นญ์„ ์‹œ์ผœ๋„ ๋‘ ๊ฐ€์ง€ ๊ฒฝ์šฐ ๋ฐ–์— ์—†๋‹ค. ํ•˜์ง€๋งŒ 2์Œ์”ฉ x์™€ y ๊ฐ’์ด ๊ฐ๊ฐ y์™€ x ๊ฐ’๊ณผ ๊ฐ™์œผ๋ฏ€๋กœ 1๊ฐœ์˜ ์ขŒํ‘œ๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

 

Fig_2_x, Fig_2_y

= ํšŒ์ „, ๋Œ€์นญ์„ ์‹œ์ผœ๋„ ํ•œ ๊ฐ€์ง€ ๊ฒฝ์šฐ ๋ฐ–์— ์—†๋‹ค. 

 

Fig_3_x, Fig_3_y

= ํšŒ์ „, ๋Œ€์นญ์„ ์‹œํ‚ค๋ฉด 8๊ฐ€์ง€์˜ ๊ฒฝ์šฐ๊ฐ€ ์กด์žฌํ•œ๋‹ค. ํ•˜์ง€๋งŒ 2์Œ์”ฉ x์™€ y๊ฐ’์ด ๊ฐ๊ฐ y์™€ x๊ฐ’๊ณผ ๊ฐ™์œผ๋ฏ€๋กœ 4๊ฐœ์˜ ์ขŒํ‘œ๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

 

Fig_4_x, Fig_4_y

= ํšŒ์ „, ๋Œ€์นญ์„ ์‹œํ‚ค๋ฉด 4๊ฐ€์ง€์˜ ๊ฒฝ์šฐ๊ฐ€ ์กด์žฌํ•œ๋‹ค. 

 

Fig_5_x, Fig_5_y

= ํšŒ์ „, ๋Œ€์นญ์‹œํ‚ค๋ฉด 4๊ฐ€์ง€์˜ ๊ฒฝ์šฐ๊ฐ€ ์กด์žฌํ•œ๋‹ค. ํ•˜์ง€๋งŒ 2์Œ์”ฉ x์™€ y๊ฐ’์ด ๊ฐ๊ฐ y์™€ x ๊ฐ’๊ณผ ๊ฐ™์œผ๋ฏ€๋กœ 2๊ฐœ์˜ ์ขŒํ‘œ๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

 

 

 

  • ์„ธ๋กœ n, ๊ฐ€๋กœ m ์ž…๋ ฅ
  • arr : ์ข…์ด์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜ ์ž…๋ ฅ
  • result = ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ๊ฐ€ ๋†“์ธ ์นธ์— ์“ฐ์ธ ์ˆ˜๋“ค์˜ ํ•ฉ์˜ ์ตœ๋Œ“๊ฐ’
  • Fig_n_x, Fig_n_y : ๊ฐ ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ์˜ ์ขŒํ‘œ
  • Fig_n_x, Fig_n_y๋ฅผ ํ†ตํ•ด ๊ฐ ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ๊ฐ€ ๋†“์ธ ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๋“ค์˜ ํ•ฉ์„ ๊ตฌํ•˜์—ฌ ํ•ฉ์ด ์ตœ๋Œ€์ธ ๊ฐ’์„ ๊ตฌํ•ด์ค€๋‹ค.
  • result ์ถœ๋ ฅ

 

โ“ ์™œ ํ‹€๋ ธ๋Š”๊ฐ€?

์ดˆ๊ธฐํ™”ํ•ด์ฃผ๋Š” ์œ„์น˜๋ฅผ ์ž˜๋ชป ์„ค์ •ํ•˜์—ฌ ํ‹€๋ ธ๋‹ค. ๊ฐ„๋‹จ..? ํ•˜๊ฒŒ ํ•ด๊ฒฐ~

 

 


์ƒ๊ฐ๐Ÿค”

 

๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ ์šฉ์‹œ์ผœ ๋‹ต์„ ๊ตฌํ•ด๋„ ์‹œ๊ฐ„ ์ดˆ๊ณผ๋ฅผ ํ”ผํ•ด ๊ฐˆ ์ˆ˜ ์žˆ์„๊นŒ ํ–ˆ๋Š”๋ฐ ํ†ต๊ณผํ–ˆ๋‹ค ใ…Žใ…Ž