๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 7569_ํ† ๋งˆํ† 

๋ฟŒ์•ผ._. 2022. 3. 22. 22:40

Gold V

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

<ํ† ๋งˆํ† >

๋ฌธ์ œ 

 

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

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

 

์ž…๋ ฅ

 

์ฒซ ์ค„์—๋Š” ์ƒ์ž์˜ ํฌ๊ธฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋‘ ์ •์ˆ˜ M, N๊ณผ ์Œ“์•„ ์˜ฌ๋ ค์ง€๋Š” ์ƒ์ž์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” H๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. M์€ ์ƒ์ž์˜ ๊ฐ€๋กœ ์นธ์˜ ์ˆ˜, N์€ ์ƒ์ž์˜ ์„ธ๋กœ ์นธ์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹จ, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ๋Š” ๊ฐ€์žฅ ๋ฐ‘์˜ ์ƒ์ž๋ถ€ํ„ฐ ๊ฐ€์žฅ ์œ„์˜ ์ƒ์ž๊นŒ์ง€์— ์ €์žฅ๋œ ํ† ๋งˆํ† ๋“ค์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ฆ‰, ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ํ•˜๋‚˜์˜ ์ƒ์ž์— ๋‹ด๊ธด ํ† ๋งˆํ† ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ์ค„์—๋Š” ์ƒ์ž ๊ฐ€๋กœ์ค„์— ๋“ค์–ด์žˆ๋Š” ํ† ๋งˆํ† ๋“ค์˜ ์ƒํƒœ๊ฐ€ M๊ฐœ์˜ ์ •์ˆ˜๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ •์ˆ˜ 1์€ ์ต์€ ํ† ๋งˆํ† , ์ •์ˆ˜ 0 ์€ ์ต์ง€ ์•Š์€ ํ† ๋งˆํ† , ์ •์ˆ˜ -1์€ ํ† ๋งˆํ† ๊ฐ€ ๋“ค์–ด์žˆ์ง€ ์•Š์€ ์นธ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ด๋Ÿฌํ•œ N๊ฐœ์˜ ์ค„์ด H๋ฒˆ ๋ฐ˜๋ณตํ•˜์—ฌ ์ฃผ์–ด์ง„๋‹ค.
ํ† ๋งˆํ† ๊ฐ€ ํ•˜๋‚˜ ์ด์ƒ ์žˆ๋Š” ๊ฒฝ์šฐ๋งŒ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„๋‹ค.

 

์ถœ๋ ฅ 

 

์—ฌ๋Ÿฌ๋ถ„์€ ํ† ๋งˆํ† ๊ฐ€ ๋ชจ๋‘ ์ต์„ ๋•Œ๊นŒ์ง€ ์ตœ์†Œ ๋ฉฐ์น ์ด ๊ฑธ๋ฆฌ๋Š”์ง€๋ฅผ ๊ณ„์‚ฐํ•ด์„œ ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค. ๋งŒ์•ฝ, ์ €์žฅ๋  ๋•Œ๋ถ€ํ„ฐ ๋ชจ๋“  ํ† ๋งˆํ† ๊ฐ€ ์ต์–ด์žˆ๋Š” ์ƒํƒœ์ด๋ฉด 0์„ ์ถœ๋ ฅํ•ด์•ผ ํ•˜๊ณ , ํ† ๋งˆํ† ๊ฐ€ ๋ชจ๋‘ ์ต์ง€๋Š” ๋ชปํ•˜๋Š” ์ƒํ™ฉ์ด๋ฉด -1์„ ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค.

 

 

๋ฌธ์ œ ํ’€์ด

   - my solution

import sys
from collections import deque

def bfs(graph, queue, visited, depth, n):
    dx=[-1,1,0,0, n, -n] # ์ƒ,ํ•˜,์ขŒ,์šฐ,์•„๋ž˜์ธต,์œ„์ธต
    dy=[0,0,-1,1, 0, 0]
    while queue:
        temp=queue.popleft()
        for i in range(6):
            x=temp[0]+dx[i]
            y=temp[1]+dy[i]
            flag=True
            if x>=0 and x<len(graph) and y>=0 and y<len(graph[0]): #ํ† ๋งˆํ†  ์ฐฝ๊ณ  ๋ฒ”์œ„ ์•ˆ
                if visited[x][y]==0 : # ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜๋‹ค๋ฉด
                    if dx[i]!=n and dx[i]!=-n: # ์ƒํ•˜์ขŒ์šฐ==๊ฐ™์€ ์ธต
                        if temp[0]//n != x//n:
                            flag=False
                    if flag==True:
                        queue.append([x,y])
                        visited[x][y]=1
                        depth[x][y]=depth[temp[0]][temp[1]]+1

if __name__ =='__main__':
    m,n,h=map(int ,sys.stdin.readline().split())

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

    visited=[[0]*m for i in range(n*h)] # ๋ฐฉ๋ฌธ ์—ฌ๋ถ€
    depth=[[0]*m for i in range(n*h)] # day
    start=deque([])

    for i in range(n*h):
        for j in range(m):
            if graph[i][j]==-1: # ํ† ๋งˆํ† ๊ฐ€ ๋“ค์–ด์žˆ์ง€ ์•Š์Œ
                visited[i][j]=1
            if visited[i][j]==0 and graph[i][j]==1: # ๋ฐฉ๋ฌธx, ์ต์€ ํ† ๋งˆํ† 
                start.append([i,j])
                visited[i][j]=1
    bfs(graph, start, visited, depth, n)

    answer=-1
    flag=False # ๋ชจ๋‘ ์ต์ง€ ๋ชปํ•˜๋Š” ๊ฒฝ์šฐ ํŒ๋ณ„
    for i in range(n*h):
        if flag == True:
            answer=-1
            break
        for j in range(m):
            if visited[i][j]==0: # ์ต์ง€ ๋ชปํ•œ ํ† ๋งˆํ† 
                flag=True
                break
            else: # ์ตœ์†Œ ๋‚ ์งœ ๊ตฌํ•˜๊ธฐ
                if answer<depth[i][j]:
                    answer=depth[i][j]

    print(answer)

 

  • bfs (ํ† ๋งˆํ†  ์ •๋ณด,  queue , ๋ฐฉ๋ฌธ ์—ฌ๋ถ€ list, day, n)
    : dx, dy = ์ƒ, ํ•˜, ์ขŒ, ์šฐ, ์œ„์ธต, ์•„๋ž˜์ธต ํƒ์ƒ‰
    : queue๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณต -> ์ œ์ผ ์ฒ˜์Œ ๊ฐ’์„ pop -> ์ƒ, ํ•˜, ์ขŒ, ์šฐ, ์œ„์ธต, ์•„๋ž˜์ธต์„ ํ™•์ธํ•˜์—ฌ ํ† ๋งˆํ†  ์ƒ์ž ๋ฒ”์œ„์— ์†ํ•˜๋ฉด -> ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜๋‹ค๋ฉด -> ์ƒํ•˜์ขŒ์šฐ์ธ ๊ฒฝ์šฐ ๊ฐ™์€ ์ธต์ด๋ผ๋ฉด queue์— ์ถ”๊ฐ€, ๋ฐฉ๋ฌธ o, ์ด๋™ํ•  ์œ„์น˜์˜ depth = ํ˜„์žฌ ์œ„์น˜์˜ depth +1 
  • main
    : m, n, h ์ž…๋ ฅ
    : ํ† ๋งˆํ†  ์ •๋ณด ์ž…๋ ฅ
    : graph = ํ† ๋งˆํ†  ์ •๋ณด
     visited = ๋ฐฉ๋ฌธ ์—ฌ๋ถ€ 
     depth = ์ตœ์†Œ ์ผ์ˆ˜ ๊ตฌํ•˜๊ธฐ ์œ„ํ•œ day ์ €์žฅ
     answer= ์ตœ์†Œ ๋‚ ์งœ
    : ํ† ๋งˆํ† ๊ฐ€ ๋“ค์–ด์žˆ์ง€ ์•Š์€ ๊ณณ์€ bfs ํ•จ์ˆ˜์—์„œ ์˜ํ–ฅ๋ฐ›์ง€ ์•Š๋„๋ก visited๋ฅผ 1๋กœ ์„ค์ •
    : ํ† ๋งˆํ†  ์ •๋ณด ์ „์ฒด๋ฅผ ํƒ์ƒ‰ํ•˜์—ฌ ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜์œผ๋ฉฐ ์ต์€ ํ† ๋งˆํ† ๋ฅผ queue์— ์ถ”๊ฐ€ ๋ฐ ๋ฐฉ๋ฌธ o
    : bfs ํ•จ์ˆ˜ ํ˜ธ์ถœ
    : ๋ฐฉ๋ฌธ ์—ฌ๋ถ€ list๋ฅผ ์ „์ฒด ํƒ์ƒ‰ํ•˜์—ฌ 0์ด ์กด์žฌํ•˜๋ฉด = ํ† ๋งˆํ† ๊ฐ€ ๋ชจ๋‘ ์ต์ง€ ๋ชปํ•˜๋Š” ๊ฒฝ์šฐ -> -1 ์ถœ๋ ฅ
     0์ด ์—†๋‹ค๋ฉด depth ์ค‘์—์„œ ๊ฐ€์žฅ ํฐ ๊ฐ’ ์ฐพ์•„์„œ ์ถœ๋ ฅ = ์ตœ์†Œ ์ผ์ˆ˜

๋ฐ”๋กœ ์•ž ๋ฌธ์ œ์—์„œ ํ•ด๊ฒฐํ–ˆ๋˜ 7576 ํ† ๋งˆํ†  ๋ฌธ์ œ์™€ ๋งค์šฐ ๋น„์Šทํ•œ ๋ฌธ์ œ์˜€๋‹ค.

7576 ์—์„œ๋Š” ํ† ๋งˆํ†  ์ฐฝ๊ณ ๊ฐ€ ํ•œ ์ธต์ด์—ˆ๋‹ค๋ฉด 7569 ์—์„œ๋Š” ํ† ๋งˆํ†  ์ฐฝ๊ณ ๊ฐ€ ์—ฌ๋Ÿฌ ์ธต ์žˆ๋‹ค๋Š” ์ ์ด ๋‹ค๋ฅธ ๊ฒƒ ๋ง๊ณ ๋Š” ๋˜‘๊ฐ™์•˜๋‹ค.

์ƒํ•˜์ขŒ์šฐ๋ฅผ ํŒ๋ณ„ํ•  ๋•Œ ๊ฐ™์€ ์ธต ํ† ๋งˆํ†  ์ฐฝ๊ณ ์ธ์ง€ ํ™•์ธํ•˜๋Š” ๊ฒƒ๋งŒ ์ถ”๊ฐ€ํ•˜๋ฉด ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค. 

 

 

โ“ ์ฒ˜์Œ์— ์™œ ํ‹€๋ ธ๋Š”๊ฐ€?

์—ฌ๋Ÿฌ ์ธต์˜ ํ† ๋งˆํ†  ์ฐฝ๊ณ ๊ฐ€ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์ƒ, ํ•˜, ์ขŒ, ์šฐ, ์œ„์ธต, ์•„๋ž˜์ธต์„ ํŒ๋ณ„ํ•  ๋•Œ ๊ณ ๋ คํ•ด์•ผ ํ•  ์ ์„ ๋†“์ณค๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์ƒ, ํ•˜, ์ขŒ, ์šฐ ํŒ๋ณ„ ์‹œ ๋‹ค๋ฅธ ์ธต์ธ๋ฐ ๋‹จ์ง€, ํ† ๋งˆํ†  ์ฐฝ๊ณ  ๋ฒ”์œ„์— ๋งž๋‹ค๊ณ  ๊ณ„์‚ฐํ•ด์ฃผ๋ฉด ๋‹ค๋ฅธ ๊ฒฐ๊ณผ๊ฐ€ ๋‚˜์˜ค๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ ์ƒ, ํ•˜, ์ขŒ, ์šฐ ํŒ๋ณ„ ์‹œ ๊ฐ™์€ ์ธต์˜ ํ† ๋งˆํ†  ์ฐฝ๊ณ ์ธ์ง€๋ฅผ ํŒ๋ณ„ํ•˜๋Š” if ๋ฌธ์„ ๋„ฃ์–ด ํ†ต๊ณผํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.

 

 


์ƒ๊ฐ๐Ÿค”

 

๋ฐ”๋กœ ์•ž์— ํ’€์—ˆ๋˜ ๋ฌธ์ œ์™€ ์ฝ”๋“œ๋„ ๋น„์Šทํ•˜์—ฌ ๋จธ์“ฑํ•˜๊ธด ํ•˜์ง€๋งŒ ๊ทธ๋ž˜๋„ ํ†ต๊ณผํ–ˆ๋‹ค!

๋””๋ฒ„๊น…ํ•˜๋Š๋ผ ํž˜๋“ค์—ˆ๋‹ค ๐Ÿ˜ฅ

 


 

 

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

[Baekjoon] 1068_ํŠธ๋ฆฌ  (0) 2022.03.25
[Baekjoon] 3190_๋ฑ€  (0) 2022.03.23
[Baekjoon] 7576_ํ† ๋งˆํ†   (0) 2022.03.21
[Baekjoon] 10026_์ ๋ก์ƒ‰์•ฝ  (0) 2022.03.20
[Baekjoon] 4889_์•ˆ์ •์ ์ธ ๋ฌธ์ž์—ด  (0) 2022.03.18