Breath everything
Home
  • 분류 전체보기 (133)
    • 취미 (29)
    • 영어 (30)
      • Daily 영어표현 (24)
      • TOEIC_OPIC (6)
    • IT (47)
      • 따로 공부 (13)
      • 외부강의 (3)
      • 자료구조 & 알고리즘 (20)
      • 백준 (9)
      • 프로그래머스 (2)
    • 자격증 (5)
    • 기타 (19)
    • 복기 (1)
      • 코딩테스트 (1)
Home
  • 분류 전체보기 (133)
    • 취미 (29)
    • 영어 (30)
      • Daily 영어표현 (24)
      • TOEIC_OPIC (6)
    • IT (47)
      • 따로 공부 (13)
      • 외부강의 (3)
      • 자료구조 & 알고리즘 (20)
      • 백준 (9)
      • 프로그래머스 (2)
    • 자격증 (5)
    • 기타 (19)
    • 복기 (1)
      • 코딩테스트 (1)
블로그 내 검색

Breath everything

이것 저것

  • IT/백준

    [백준] 1697 숨바꼭질(Python)

    2021. 10. 12.

    by. ziasu

    반응형

    1. 생각 정리

    • 수빈이의 위치에서 동생의 위치까지 무조건 동생과 가까워지는 루트만 따라가면 오히려 시간이 오래 걸릴 수도 있다.
    • 그러므로 각 프로세스마다 (프로세스 단계 * 3)만큼 다양해지는 모든 경우를 고려하여 그중 동생의 위치까지 갔을 때 지금까지 소요된 시간 출력
    • 크기가 100001인 일차원 리스트에 각 위치마다 시간이 얼마나 걸렸는지 갱신하며 동생을 찾을 수 있는 가장 빠른 시간을 구하기

     

    2.  메모리 초과 코드

    #메모리 초과
    from collections import deque
    
    N,K = map(int, input().split())
    
    def bfs(n,k):
        q = deque([N])
        result = 0
        count = 1
        while q:
            pos = q.popleft()
            if pos == K:
                print(result)
                break
            q.append(pos+1)
            q.append(pos-1)
            q.append(2*pos)
            if len(q) == 3**count:
                count+=1
                result+=1                   
    bfs(N,K)

     

    3. 성공 코드

    from collections import deque
    
    MAX = 100001
    N,K = map(int, input().split())
    mapp = [0]*MAX
    def bfs():
        q = deque([N])
        while q:
            pos = q.popleft()
            if pos == K:
                return mapp[pos]
            for next_pos in (pos-1, pos+1, pos*2):
                if 0<=next_pos<MAX and not mapp[next_pos]:
                    mapp[next_pos] = mapp[pos]+1
                    q.append(next_pos)
                    
    print(bfs())
    반응형
    저작자표시 (새창열림)

    'IT > 백준' 카테고리의 다른 글

    [백준] 2655 가장높은탑쌓기(Python)  (0) 2021.10.23
    [백준] 1012 유기농 배추(Python)  (0) 2021.10.13
    [백준] 1260 DFS와 BFS(Python)  (0) 2021.10.12
    [백준] 11053 가장 긴 증가하는 부분 수열(Python)  (0) 2021.10.11

    댓글

    관련글

    • [백준] 2655 가장높은탑쌓기(Python) 2021.10.23
    • [백준] 1012 유기농 배추(Python) 2021.10.13
    • [백준] 1260 DFS와 BFS(Python) 2021.10.12
    • [백준] 11053 가장 긴 증가하는 부분 수열(Python) 2021.10.11
    맨 위로
전체 글 보기
Tistory 로그인
Tistory 로그아웃
로그아웃 글쓰기 관리

Today

Total

Powered by ⓒ Kakao Corp.

Designed by Nana
블로그 이미지
ziasu

티스토리툴바