๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 23288_์ฃผ์‚ฌ์œ„ ๊ตด๋ฆฌ๊ธฐ 2

๋ฟŒ์•ผ._. 2022. 5. 11. 17:06

Gold III

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

<์ฃผ์‚ฌ์œ„ ๊ตด๋ฆฌ๊ธฐ 2>

๋ฌธ์ œ 

 

ํฌ๊ธฐ๊ฐ€ N×M์ธ ์ง€๋„๊ฐ€ ์กด์žฌํ•œ๋‹ค. ์ง€๋„์˜ ์˜ค๋ฅธ์ชฝ์€ ๋™์ชฝ, ์œ„์ชฝ์€ ๋ถ์ชฝ์ด๋‹ค. ์ง€๋„์˜ ์ขŒํ‘œ๋Š” (r, c)๋กœ ๋‚˜ํƒ€๋‚ด๋ฉฐ, r๋Š” ๋ถ์ชฝ์œผ๋กœ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜, c๋Š” ์„œ์ชฝ์œผ๋กœ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜์ด๋‹ค. ๊ฐ€์žฅ ์™ผ์ชฝ ์œ„์— ์žˆ๋Š” ์นธ์˜ ์ขŒํ‘œ๋Š” (1, 1)์ด๊ณ , ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜์— ์žˆ๋Š” ์นธ์˜ ์ขŒํ‘œ๋Š” (N, M)์ด๋‹ค. ์ด ์ง€๋„์˜ ์œ„์— ์ฃผ์‚ฌ์œ„๊ฐ€ ํ•˜๋‚˜ ๋†“์—ฌ์ ธ ์žˆ์œผ๋ฉฐ, ์ฃผ์‚ฌ์œ„์˜ ๊ฐ ๋ฉด์—๋Š” 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 6๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜๊ฐ€ ํ•˜๋‚˜์”ฉ ์žˆ๋‹ค. ์ฃผ์‚ฌ์œ„ ํ•œ ๋ฉด์˜ ํฌ๊ธฐ์™€ ์ง€๋„ ํ•œ ์นธ์˜ ํฌ๊ธฐ๋Š” ๊ฐ™๊ณ , ์ฃผ์‚ฌ์œ„์˜ ์ „๊ฐœ๋„๋Š” ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

 

  2
4 1 3
  5
  6

 

์ฃผ์‚ฌ์œ„๋Š” ์ง€๋„ ์œ„์— ์œ— ๋ฉด์ด 1์ด๊ณ , ๋™์ชฝ์„ ๋ฐ”๋ผ๋ณด๋Š” ๋ฐฉํ–ฅ์ด 3์ธ ์ƒํƒœ๋กœ ๋†“์—ฌ์ ธ ์žˆ์œผ๋ฉฐ, ๋†“์—ฌ์ ธ ์žˆ๋Š” ๊ณณ์˜ ์ขŒํ‘œ๋Š” (1, 1)์ด๋‹ค. ์ง€๋„์˜ ๊ฐ ์นธ์—๋„ ์ •์ˆ˜๊ฐ€ ํ•˜๋‚˜์”ฉ ์žˆ๋‹ค. ๊ฐ€์žฅ ์ฒ˜์Œ์— ์ฃผ์‚ฌ์œ„์˜ ์ด๋™ ๋ฐฉํ–ฅ์€ ๋™์ชฝ์ด๋‹ค. ์ฃผ์‚ฌ์œ„์˜ ์ด๋™ ํ•œ ๋ฒˆ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ์ด๋ฃจ์–ด์ง„๋‹ค.

1. ์ฃผ์‚ฌ์œ„๊ฐ€ ์ด๋™ ๋ฐฉํ–ฅ์œผ๋กœ ํ•œ ์นธ ๊ตด๋Ÿฌ๊ฐ„๋‹ค. ๋งŒ์•ฝ, ์ด๋™ ๋ฐฉํ–ฅ์— ์นธ์ด ์—†๋‹ค๋ฉด, ์ด๋™ ๋ฐฉํ–ฅ์„ ๋ฐ˜๋Œ€๋กœ ํ•œ ๋‹ค์Œ ํ•œ ์นธ ๊ตด๋Ÿฌ๊ฐ„๋‹ค.
2. ์ฃผ์‚ฌ์œ„๊ฐ€ ๋„์ฐฉํ•œ ์นธ (x, y)์— ๋Œ€ํ•œ ์ ์ˆ˜๋ฅผ ํš๋“ํ•œ๋‹ค.
3. ์ฃผ์‚ฌ์œ„์˜ ์•„๋žซ๋ฉด์— ์žˆ๋Š” ์ •์ˆ˜ A์™€ ์ฃผ์‚ฌ์œ„๊ฐ€ ์žˆ๋Š” ์นธ (x, y)์— ์žˆ๋Š” ์ •์ˆ˜ B๋ฅผ ๋น„๊ตํ•ด ์ด๋™ ๋ฐฉํ–ฅ์„ ๊ฒฐ์ •ํ•œ๋‹ค.
     A > B์ธ ๊ฒฝ์šฐ ์ด๋™ ๋ฐฉํ–ฅ์„ 90๋„ ์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „์‹œํ‚จ๋‹ค.
     A < B์ธ ๊ฒฝ์šฐ ์ด๋™ ๋ฐฉํ–ฅ์„ 90๋„ ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „์‹œํ‚จ๋‹ค.
     A = B์ธ ๊ฒฝ์šฐ ์ด๋™ ๋ฐฉํ–ฅ์— ๋ณ€ํ™”๋Š” ์—†๋‹ค.

์นธ (x, y)์— ๋Œ€ํ•œ ์ ์ˆ˜๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค. (x, y)์— ์žˆ๋Š” ์ •์ˆ˜๋ฅผ B๋ผ๊ณ  ํ–ˆ์„ ๋•Œ, (x, y)์—์„œ ๋™์„œ๋‚จ๋ถ ๋ฐฉํ–ฅ์œผ๋กœ ์—ฐ์†ํ•ด์„œ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์˜ ์ˆ˜ C๋ฅผ ๋ชจ๋‘ ๊ตฌํ•œ๋‹ค. ์ด๋•Œ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์—๋Š” ๋ชจ๋‘ ์ •์ˆ˜ B๊ฐ€ ์žˆ์–ด์•ผ ํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ ์ ์ˆ˜๋Š” B์™€ C๋ฅผ ๊ณฑํ•œ ๊ฐ’์ด๋‹ค.

๋ณด๋“œ์˜ ํฌ๊ธฐ์™€ ๊ฐ ์นธ์— ์žˆ๋Š” ์ •์ˆ˜, ์ฃผ์‚ฌ์œ„์˜ ์ด๋™ ํšŸ์ˆ˜ K๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ ์ด๋™์—์„œ ํš๋“ํ•˜๋Š” ์ ์ˆ˜์˜ ํ•ฉ์„ ๊ตฌํ•ด๋ณด์ž.

์ด ๋ฌธ์ œ์˜ ์˜ˆ์ œ 1๋ถ€ํ„ฐ 7์€ ๊ฐ™์€ ์ง€๋„์—์„œ ์ด๋™ํ•˜๋Š” ํšŸ์ˆ˜๋งŒ ์ฆ๊ฐ€์‹œํ‚ค๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋‹ค. ์˜ˆ์ œ 8์€ ๊ฐ™์€ ์ง€๋„์—์„œ ์ด๋™ํ•˜๋Š” ํšŸ์ˆ˜๋ฅผ ๋งค์šฐ ํฌ๊ฒŒ ๋งŒ๋“ค์—ˆ๋‹ค.

 

 

์ž…๋ ฅ

 

์ฒซ์งธ ์ค„์— ์ง€๋„์˜ ์„ธ๋กœ ํฌ๊ธฐ N, ๊ฐ€๋กœ ํฌ๊ธฐ M (2 ≤ N, M ≤ 20), ๊ทธ๋ฆฌ๊ณ  ์ด๋™ํ•˜๋Š” ํšŸ์ˆ˜ K (1 ≤ K ≤ 1,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. 

๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์ง€๋„์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๊ฐ€ ๋ถ์ชฝ๋ถ€ํ„ฐ ๋‚จ์ชฝ์œผ๋กœ, ๊ฐ ์ค„์€ ์„œ์ชฝ๋ถ€ํ„ฐ ๋™์ชฝ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ง€๋„์˜ ๊ฐ ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๋Š” 10 ๋ฏธ๋งŒ์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.

 

 

์ถœ๋ ฅ 

 

์ฒซ์งธ ์ค„์— ๊ฐ ์ด๋™์—์„œ ํš๋“ํ•˜๋Š” ์ ์ˆ˜์˜ ํ•ฉ์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

 

๋ฌธ์ œ ํ’€์ด

   - my solution (Python)

import sys
from collections import deque

def throw_dice(a,b,c,d,e,f):
    temp=[0,0,0,0,0,0]
    temp[0]=dice[a]
    temp[1]=dice[b]
    temp[2]=dice[c]
    temp[3]=dice[d]
    temp[4]=dice[e]
    temp[5]=dice[f]
    return temp

def change_direction(num, A, B):
    if A>B: # ์‹œ๊ณ„ ๋ฐฉํ–ฅ
        num+=1
        if num>3:
            num=0
    elif A<B: # ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ
        num-=1
        if num<0:
            num=3
    return num

def get_score(arr, start):
    c=1
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    queue=deque([start])
    visited=[[0]*len(arr[0]) for i in range(len(arr))] # ๋ฐฉ๋ฌธ ์—ฌ๋ถ€
    visited[start[0]][start[1]]=1

    while queue:
        temp=queue.popleft()
        for i in range(4):
            x=temp[0]+dx[i]
            y=temp[1]+dy[i]
            if 0<=x<len(arr) and 0<=y<len(arr[0]):
                if arr[x][y]==arr[temp[0]][temp[1]] and visited[x][y]==0:
                    queue.append([x,y])
                    visited[x][y]=1
                    c+=1
    return c

if __name__=='__main__':
    n,m,k=map(int,sys.stdin.readline().split()) # ์„ธ๋กœ, ๊ฐ€๋กœ, ์ด๋™ํ•˜๋Š” ํšŸ์ˆ˜

    arr=[]
    for i in range(n): # ์ง€๋„
        arr.append(list(map(int,sys.stdin.readline().split())))

    dice=[2,1,5,6,4,3]
    direction=1 # 0 = ๋ถ, 1= ๋™, 2= ๋‚จ, 3= ์„œ

    x=0 # ์ขŒํ‘œ
    y=0
    cnt=0 # ์ด๋™ํ•œ ํšŸ์ˆ˜
    result=0
    while cnt<k:
        flag = False
        if direction==0: # ๋ถ
            if x-1>=0:
                flag=True
                x-=1
                dice=throw_dice(1,2,3,0,4,5)
            else: 
                direction=2

        elif direction==1: # ๋™
            if y+1<m:
                flag = True
                y+=1
                dice=throw_dice(0,4,2,5,3,1)
            else:
                direction=3

        elif direction==2: # ๋‚จ
            if x+1<n:
                flag = True
                x+=1
                dice=throw_dice(3,0,1,2,4,5)
            else:
                direction=0
        else: # ์„œ
            if y-1>=0:
                flag = True
                y-=1
                dice=throw_dice(0,5,2,4,1,3)
            else:
                direction=1
        if flag==True:
            result+=(get_score(arr, [x,y]) * arr[x][y]) # ์ ์ˆ˜
            direction = change_direction(direction, dice[3], arr[x][y]) # ๋ฐฉํ–ฅ ๊ฒฐ์ •
            cnt += 1

    print(result)

 

 

1) ์ฃผ์‚ฌ์œ„ ์ „๊ฐœ๋„ -> ๋ฆฌ์ŠคํŠธ๋กœ ์ €์žฅ

 

2) ์ฃผ์‚ฌ์œ„๋ฅผ ๊ตด๋ ธ์„ ๋•Œ

 

์ฃผ์‚ฌ์œ„๋ฅผ ๋™์„œ๋‚จ๋ถ ๋ฐฉํ–ฅ์œผ๋กœ ๊ตด๋ ค์•ผ ํ•˜๋ฏ€๋กœ, ์ฃผ์‚ฌ์œ„๋ฅผ ๊ตด๋ ธ์„ ๋•Œ ๋ฆฌ์ŠคํŠธ ๊ฐ’์ด ๋ณ€ํ•˜๋Š” ๊ฒƒ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

 

* ํ™”์‚ดํ‘œ ๋ฐฉํ–ฅ ์ฃผ์˜

 

 

๋™
์„œ
๋ถ
๋‚จ

3) direction ์„ค์ •

 

0 = ๋ถ

1 = ๋™

2 = ๋‚จ

3 = ์„œ

๋กœ ์„ค์ •ํ•˜์—ฌ 90๋„ ์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•  ๊ฒฝ์šฐ +1, 90๋„ ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•  ๊ฒฝ์šฐ -1๋กœ ๋ฐฉํ–ฅ์„ ๋ณ€๊ฒฝํ•  ์ˆ˜ ์žˆ๋„๋ก ํ•ด์คฌ๋‹ค.

 

 

  • throw_dice
    : ๊ฐ ๋ฐฉํ–ฅ์œผ๋กœ ์ฃผ์‚ฌ์œ„๋ฅผ ๊ตด๋ ธ์„ ๋•Œ ์ฃผ์‚ฌ์œ„ ์ „๊ฐœ๋„๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ ํ•จ์ˆ˜
  • change_direction ( ๋ฐฉํ–ฅ, ์ฃผ์‚ฌ์œ„ ์•„๋žซ๋ฉด, ์ฃผ์‚ฌ์œ„๊ฐ€ ์žˆ๋Š” ์นธ)
    : ์ฃผ์‚ฌ์œ„ ์•„๋žซ๋ฉด > ์ฃผ์‚ฌ์œ„ ์žˆ๋Š” ์นธ = ์‹œ๊ณ„ ๋ฐฉํ–ฅ
    : ์ฃผ์‚ฌ์œ„ ์•„๋žซ๋ฉด < ์ฃผ์‚ฌ์œ„ ์žˆ๋Š” ์นธ = ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ
  • get_score ( ์ง€๋„, ์‹œ์ž‘ ์ขŒํ‘œ )
    : c = ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์˜ ์ˆ˜
    : visited = ๋ฐฉ๋ฌธ ์—ฌ๋ถ€
    : queue๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณต -> queue์—์„œ ์ขŒํ‘œ๋ฅผ ๊บผ๋‚ธ ํ›„ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ํƒ์ƒ‰ํ•˜์—ฌ ๊ทธ ์นธ์˜ ๊ฐ’๊ณผ ์ด๋™ํ•  ์นธ์˜ ๊ฐ’์ด ๊ฐ™์œผ๋ฉฐ ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜๋‹ค๋ฉด queue์— ์ €์žฅ ๋ฐ ๋ฐฉ๋ฌธ ํ‘œ์‹œ, ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์˜ ์ˆ˜ +1
  • Main
    : ์ง€๋„์˜ ์„ธ๋กœ, ๊ฐ€๋กœ, ์ด๋™ํ•˜๋Š” ํšŸ์ˆ˜ ์ž…๋ ฅ
    : arr (์ง€๋„) ์ •๋ณด ์ž…๋ ฅ
    : dice = ์ฃผ์‚ฌ์œ„ ์ „๊ฐœ๋„ ์ •๋ณด ์ €์žฅ
    : direction = ๋ฐฉํ–ฅ ์ €์žฅ ( 0 = ๋ถ, 1 = ๋™, 2 = ๋‚จ, 3 = ์„œ )
    : x, y = ์ขŒํ‘œ , cnt = ์ด๋™ํ•œ ํšŸ์ˆ˜, result = ์ ์ˆ˜
    : ์ด๋™ํ•œ ํšŸ์ˆ˜๊ฐ€ ์ด๋™ํ•˜๋Š” ํšŸ์ˆ˜๋ณด๋‹ค ์ž‘์œผ๋ฉด ๊ณ„์†ํ•ด์„œ ๋ฐ˜๋ณต -> ๋ฐฉํ–ฅ๋Œ€๋กœ ์›€์ง์ผ ์ขŒํ‘œ๋ฅผ ๊ตฌํ•œ ํ›„ ์ง€๋„ ๋ฒ”์œ„ ์•ˆ์ด๋ผ๋ฉด ์ขŒํ‘œ ์ด๋™ ๋ฐ ๊ตด๋ฆฐ ์ฃผ์‚ฌ์œ„ ์ „๊ฐœ๋„ ์ €์žฅ ํ›„ ์ ์ˆ˜, ๋‹ค์Œ ๋ฐฉํ–ฅ ๊ตฌํ•˜๊ธฐ, cnt+1, but ์ง€๋„ ๋ฒ”์œ„ ๋ฐ–์ด๋ผ๋ฉด ๋ฐ˜๋Œ€ ๋ฐฉํ–ฅ์œผ๋กœ ์ €์žฅ (์ด๋™ ๋ฐฉํ–ฅ์— ์นธ์ด ์—†๋‹ค๋ฉด ๋ฐ˜๋Œ€๋กœ ํ•œ ๋‹ค์Œ ํ•œ ์นธ ๊ตด๋Ÿฌ๊ฐ€์•ผ ํ•˜๋ฏ€๋กœ ์ง€๋„ ๋ฒ”์œ„ ๋ฐ–์ด๋ผ๋ฉด cnt+1์„ ์•ˆ ํ•ด์คŒ์œผ๋กœ์จ ํ•œ ์นธ ๊ตด๋Ÿฌ๊ฐ€๋„๋ก ํ•ด์ค€๋‹ค.)

 

 


์ƒ๊ฐ๐Ÿค”

 

 

๋ฌธ์ œ์˜ ๋‚ด์šฉ์„ ์ž˜ ์ •๋ฆฌํ•ด์„œ ๊ทธ๋Œ€๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.