광규니
광규니네
광규니
전체 방문자
오늘
어제
  • 분류 전체보기 (154)
    • 알고리즘 (100)
      • 알고리즘 개념 (2)
      • 문제 풀이 (96)
    • 주절주절 (19)
      • 자격증, 활동 후기 (4)
      • 전시회 후기 (3)
      • 이모저모 (2)
      • 회고 (3)
      • 뜨럼 (7)
    • 운영체제 (9)
    • 개발 지식 (9)
      • Apple Watch (4)
      • MySQL (2)
      • Eclipse (1)
      • XCode (1)
    • 네트워크 공부 (1)
    • 데이터베이스 공부 (5)
    • Java 공부 (7)
    • TMP (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • BOJ
  • 파이썬
  • BFS
  • DP
  • 백준
  • 다이나믹 프로그래밍
  • 합주
  • 개념
  • 컴퓨터 사이언스
  • 애플워치 앱
  • 티스토리챌린지
  • 애플워치 앱 만들기
  • 오블완
  • 프로그래머스
  • 드린이
  • 알고리즘
  • 자바
  • OS
  • 운영체제
  • 구현

최근 댓글

최근 글

티스토리

250x250
hELLO · Designed By 정상우.
광규니

광규니네

알고리즘/문제 풀이

[Python/파이썬 15684 백준] 사다리 조작

2021. 3. 28. 22:44
반응형

www.acmicpc.net/problem/15684

 

15684번: 사다리 조작

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

www.acmicpc.net

check 함수는 세로선이 자기 위치 맞게 가면 True 아니면 False

bf 함수는 재귀로 다리를 3개까지만  이어주면서 true값 비교

주석  참고하세용

import sys
input=sys.stdin.readline

n,m,h=map(int,input().split())

if m==0:
    print(0)
    sys.exit()

bridge=[[False]*n for _ in range(h)]
for _ in range(m):
    a,b=map(int,input().split())
    bridge[a-1][b-1]=True
# start는 처음 위치고 k는 사다리 타고 밑으로 내려갔을 때 위치
# 같으면 true 다르면 false
def check():
    for start in range(n):
        k=start
        for i in range(h):
            if bridge[i][k]:
                k+=1
            elif k>0 and bridge[i][k-1]:
                k-=1
            
        if start !=k:
            return False
    return True

def bf(cnt,x,y):
    global ans
    #check True면 cnt 와 ans 값 비교
    if check():
        ans=min(ans,cnt)
        return
    # cnt가 3개고 check 에서 안걸러졌으니 return
    elif cnt==3 or ans<cnt:
        return
    # 재귀로 브루트포스 알고리즘 다리 3개까지만 true
    for i in range(x,h):
        k=y if i==x else 0
        for j in range(k,n-1):
            # i,j 와 i,j+1이 둘다 false면 i,j true
            if not bridge[i][j] and not bridge[i][j+1]:
                bridge[i][j]=True
                # +2 는 j와 j+1을 이어줘서
                bf(cnt+1,i,j+2)
                bridge[i][j]=False

ans=4
bf(0,0,0)
print(ans if ans<4 else -1)
반응형
저작자표시 (새창열림)

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

[Python/파이썬 백준 1759] 암호 만들기  (0) 2021.04.03
[Python/파이썬 10819 백준] 차이를 최대로  (0) 2021.04.03
[Python/파이썬 14891 백준] 톱니바퀴  (0) 2021.03.25
[Python/파이썬 14890 백준] 경사로  (0) 2021.03.24
[Python/파이썬 14888 백준] 연산자 끼워넣기  (0) 2021.03.23
    '알고리즘/문제 풀이' 카테고리의 다른 글
    • [Python/파이썬 백준 1759] 암호 만들기
    • [Python/파이썬 10819 백준] 차이를 최대로
    • [Python/파이썬 14891 백준] 톱니바퀴
    • [Python/파이썬 14890 백준] 경사로
    광규니
    광규니
    공부 및 일상 올리기~

    티스토리툴바