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)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

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

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 사다리 조작 15684번 (python)

2021. 10. 15. 18:42

❓ 문제 - 백준 사다리 조작 15684번 - python 풀이법

출처 

(https://www.acmicpc.net/problem/15684)

 

15684번: 사다리 조작

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선

www.acmicpc.net

 

 

 

📝 문제해결법

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

  • 일단 사다리가 이미 있는 곳은 visited 리스트를 통해 방문 처리 해준다.
  • 주어진 문제에 조건에서 양 옆에 사다리가 있으면 사다리를 놓을 수 없기 때문에 사다리를 놓여질 수 있는 행과 열을 돌면서 양쪽과 해당 위치에 사다리가 없다면 사다리를 놓을 수 있는 후보군으로 두기 위해 combi 리스트에 해당 행과 열의 위치를 append 해준다.
  • check() :  사다리가 놓여져 있을 때 , 모든 열에 대해서 현재 i번째 열이 사다리를 이동해서 i번째에 도착할 수 있는지 확인할 수 있도록 한다. 구현 방식은 해당 열에 대해서 왼쪽에 만약 사다리가 놓였다면 왼쪽으로 이동하므로 now(이동된 값)을 now-1로 해주고, 만약 현재 위치에 사다리가 놓였다면 오른쪽으로 이동해야하므로 now(이동된 값)을 now+1로 해준다. 마지막에 처음 출발했던 열의 번호와 now(이동된 값)을 비교해서 True, False를 반환한다.
  • dfs() : 일단 4개 이상 사다리를 놓을 수 없기 때문에 사다리를 3번 이상 놓았을 때도 check() , 즉 모든 열의 값이 사다리를 타고 이동했을 때 자신의 열값과 이동된 값지 않다면 더이상 dfs 를 돌릴 필요 없기 때문에 return 해준다.
  • dfs() : 사다리를 놓을 수 있는 후보군의 인덱스에 다시 한번 사다리를 놓을 수 있는지 확인하고 (전에 재귀함수를 통해 사다리를 놓은 후 현재 사다리를 놓을 수 없을 수도 있음), 사다리를 놓을 수 있다면 사다리를 놓은 후 dfs 함수로 재귀를 구현한다.

 

2. 문제 풀면서 얻은 교훈

  • 사다리를 놓을 수 있을지 없을지 확인할 때 인덱스의 범위(맨 끝값)이 확인하기 힘들어서 구현이 이상한 방향으로 흘렀다. 이럴 땐, 인덱스를 접근하는 visited 리스트의 범위를 0~n+1 , 0 ~ h+1로 늘린다면 인덱스 범위 확인하는데 어려움 없이 해결할 수 있다.
  • 처음 visited 함수를 해당 곳에 사다리를 놓았다고 가정하기 위해 사다리를 놓을 때마다 visited 함수를 copy해서 시간초과가 발생했다. 구현을 다른 방식으로 바꿔 (만약 사다리를 놓았을 때 방문처리 후 dfs 다 빠져나온 후 다시 False 처리 하도록) 해결하였다.

 

 

💻 소스코드

n, m, h = map(int, input().split())
visited = [[False] * (n+1) for _ in range(h+1)]
combi = []
for _ in range(m):
    a, b = map(int, input().split())
    visited[a][b] = True

def check():
    for i in range(1, n+1):
        now = i
        for j in range(1, h+1):
            if visited[j][now-1]:
                now -= 1
            elif visited[j][now]:
                now += 1
        if now != i:
            return False
    return True

def dfs(depth, idx):
    global answer
    if depth >= answer:
        return
    if check():
        answer = depth
        return

    for c in range(idx, len(combi)):
        x, y = combi[c]
        if not visited[x][y-1] and not visited[x][y+1]:
            visited[x][y] = True
            dfs(depth+1, c+1)
            visited[x][y] = False

for i in range(1,h+1):
    for j in range(1, n):
        if not visited[i][j-1] and not visited[i][j] and not visited[i][j+1]:
            combi.append([i, j])

answer = 4
dfs(0, 0)

print(answer if answer < 4 else -1)

 

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

BOJ - 치킨 배달 15686번 (python)  (0) 2021.10.16
BOJ - 드래곤 커브 15685번 (python)  (0) 2021.10.16
BOJ - 감시 15683번 (python)  (0) 2021.10.15
BOJ - 톱니바퀴 14891번 (python, JAVA)  (0) 2021.10.15
BOJ - 경사로 14890번 (python, JAVA)  (0) 2021.10.15
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 치킨 배달 15686번 (python)
    • BOJ - 드래곤 커브 15685번 (python)
    • BOJ - 감시 15683번 (python)
    • BOJ - 톱니바퀴 14891번 (python, JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바