[삼성sw 1949번] 등산로 조정

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

bfs를 써서 등산로를 구하는 문제.

단, 조건이 좀 많이 붙었습니다.

 

1. 이전의 지나갔던 곳은 방문하면 안된다

-->'bfs구현하면 당연한 소리인데요'

이런 케이스가 있습니다.

이 문제에서 주의할 점은

산을 깍고나서

다시 돌아가는 케이스입니다.

일반적인 bfs로 구현하면

이 부분을 놓치기 쉽습니다.

저는 q안에 집합을 넣으면서

지나갔던 곳을 계속 넣어줬습니다.

 

2. 최대 K만큼 깍을 수 있다했지

꼭 K만큼 깍으라고는 안했다

-->최대 K라고 했지

K만큼 깍으라곤 안했습니다.

깍아서 현재 지점보다

한칸만 낮게 만들면 됩니다.

제가 이 부분을 구현못해서 막혔다가

문제풀이 댓글보고

'최대 K만큼이지

꼭 K만큼 깍을 필요없다'

라는 글을 보고 수정했습니다.

 

#삼성 1949 등산로조정
from collections import deque
from copy import deepcopy
dx=[0,0,1,-1]
dy=[1,-1,0,0]

def bfs(x,y):
    visited=[[[0]*2 for _ in range(N)] for _ in range(N)]
    q=deque()
    tmp=set()
    tmp.add((x,y))
    q.append((x,y,room[x][y],1,0,tmp))
    visited[x][y][0]=1
    m_cnt=1
    while q:

        px,py,now,cnt,use,road=q.popleft()
        m_cnt=max(m_cnt,cnt)
        for d in range(4):
            nx=px+dx[d]
            ny=py+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue


            #그냥 산을 가는 경우
            if room[nx][ny]<now and visited[nx][ny][use]<=cnt+1 and not (nx,ny) in road:
                visited[nx][ny][use]=cnt+1
                next_road=deepcopy(road)
                next_road.add((nx,ny))
                q.append((nx,ny,room[nx][ny],cnt+1,use,next_road))
            #산을 갈아서 갈 경우
            elif room[nx][ny]>=now and use==0 and not (nx,ny) in road:
                if room[nx][ny]-now<K and visited[nx][ny][1]<=cnt+1:
                    #최대 K만큼 깍을 수 있다했지만 굳이 K만큼 다 깍을 필요는 없다
                    #지금꺼보다 -1만큼 깍을 수 있으면 된다.
                    visited[nx][ny][1]=cnt+1
                    next_road=deepcopy(road)
                    next_road.add((nx,ny))
                    q.append((nx, ny, now-1, cnt + 1, 1,next_road))
    # for z in range(2):
    #     for sx in range(N):
    #         for sy in range(N):
    #             print(visited[sx][sy][z],end=' ')
    #         print()
    #
    #     print()
    return m_cnt

T=int(input())
for i in range(T):

    N,K=map(int,input().split())
    room=[list(map(int,input().split())) for _ in range(N)]
    max_height=0
    #1.가장 높은 봉우리 구하기
    for k in range(N):
        now_max=max(room[k])
        max_height=max(max_height,now_max)

    bo=set()
    for x in range(N):
        for y in range(N):
            if room[x][y]==max_height:
                bo.add((x,y))

    answer=0
    for bx,by in bo:
        way=bfs(bx,by)
        answer=max(answer,way)
    print("#%d %d"%((i+1),answer))

다양한 방법으로

bfs에 대해서 생각해볼 수 있는 좋은 문제입니다.

경로관련 문제풀이로 좋은 공부가 되었습니다.