developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테준비
  • 삼성코테자바풀이
  • 삼성코테자바준비
  • 삼성코테기출
  • MA모형
  • 코테파이썬
  • 통계분석
  • Arima
  • 삼성코테파이썬
  • 시계열
  • 운영체제인터럽트
  • 카카오코테
  • 백준파이썬풀이
  • 삼성코테구현문제추천
  • 삼성코테파이썬풀이
  • 삼성코테자바꿀팁
  • ARIMA모형
  • 삼성코테파이썬준비
  • 통계학
  • SW역량테스트파이썬풀이
  • c++ 빌더 패턴
  • 시계열분석
  • BOJ파이썬풀이
  • 삼성코테기출자바풀이
  • c++디자인패턴
  • 카카오코테java풀이
  • 삼성코테구현풀이
  • 데이터분석
  • AR모형
  • SW역량테스트파이썬

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

SW Expert Academy - 등산로 조정 (python)

2021. 10. 23. 18:55

❓ 문제 - SW Expert Academy 등산로 조정 python 풀이법

 

출처 

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

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

 

 

 

📝 문제해결법

1. 이 문제는 DFS + 구현으로 풀었다.

  • 일단 가장 높은 봉우리를 찾고, 모든 행과 열 돌면서 가장 높은 봉우리랑 값이 같다면 dfs를 돌아서 등산로 길이의 최대값을 갱신해야한다.
  • 4방향으로 돌면서 범위 안이고 만약 방문한 적이 없을 때, 가려는 곳이 현재 봉우리 높이보다 낮다면 해당 곳으로 방문처리 후 재귀로 들어간다. 현재 봉우리 높이 조정을 하지 않은 상태라면(flag = True) 만약 현재 봉우리 높이와 동일하거나 크다면 1 ~ k까지의 중의 현재봉우리와 이동하려는 봉우리의 차이 +1 보다 크면 파준 후, DFS 재귀로 들어가서 등산로길이를 만든다.

2. 이 문제는 DFS + 구현으로 풀었다.

  • 처음에 BFS로 풀려서 덤비다가, 이게 DFS구나 깨달았다... 앞으로 문제 풀 때, DFS, BFS 구분 확실히 해서 접근해야겠다...
  • 그리고 봉우리 높이 조정할 때 무조건 현재 봉우리와 이동할 봉우리의 높이 값의 차이 +1 만큼만 해줄 필요없이 모든 경우의 수를 탐색할 수 있도록 조정해야한다...

 

 

💻 소스코드

T = int(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(depth, x, y, val, flag):
    global max_leng
    if max_leng < depth:
        max_leng = depth

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == False:
            if board[nx][ny] < val:
                visited[nx][ny] = True
                dfs(depth+1, nx, ny, board[nx][ny], flag)
            else:
                if flag:
                    for c in range(1, k+1):
                        if (board[nx][ny]-val+1) <= c and (board[nx][ny]-c) >= 0:
                            visited[nx][ny] = True
                            dfs(depth+1, nx, ny, board[nx][ny]-c, False)
            visited[nx][ny] = False
    return

for test_case in range(1, T+1):
    n, k = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    max_leng = 0
    max_value = 0
    for i in range(n):
        max_value = max(max_value, max(board[i]))
    visited = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if board[i][j] == max_value:
                visited[i][j] = True
                dfs(1, i, j, max_value, True)
                visited[i][j] = False

    print(f'#{test_case} {max_leng}')

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - A->B 16953번 (JAVA)  (0) 2022.01.25
BOJ - 시간 관리 1263번 (JAVA)  (0) 2022.01.24
SW Expert Academy - 벌꿀 채취 (python)  (0) 2021.10.23
SW Expert Academy - 보호 필름 (python)  (0) 2021.10.23
SW Expert Academy - 디저트카페 (python)  (0) 2021.10.22
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - A->B 16953번 (JAVA)
    • BOJ - 시간 관리 1263번 (JAVA)
    • SW Expert Academy - 벌꿀 채취 (python)
    • SW Expert Academy - 보호 필름 (python)
    developer-ellen
    developer-ellen

    티스토리툴바