Baekjoon/DFS와 BFS

[백준] 5014 스타트링크 (실버1) / BFS

2023. 4. 25. 22:50

문제요약

나의 코드 및 설명

from collections import deque

def bfs(start, end):
    queue = deque()
    queue.append(start) #현재 좌표 값 큐에 추가
    visited[start] = 1 #현재 좌표 방문처리
    while queue:
        now = queue.popleft()
        if now == end: #목표 층에 도달하면
            return visited[now]-1 #룩업테이블의 현재 좌표 값 -1 
        for i in (now+u, now-d): #위로 가거나 아래로 가는 두 가지
            if 1<=i<=f and visited[i] == 0: #1층부터 옥상까지의 범위 & 아직 방문 안한 좌표
                visited[i] = visited[now] + 1 #다음 좌표 값 = 현재 좌표 값 + 1
                queue.append(i) #다음 좌표 값 큐에 추가
    return -1 #여기까지 온다면 목표 층에 도달 못한 것

f,s,g,u,d = map(int,input().split())
visited = [0] * 1000001

ans = bfs(s,g)
if ans == -1:
    print("use the stairs")
else:
    print(ans)

피드백

처음엔 DFS 멀티트리나 이진트리로 풀려다가 실패했다. BFS로 풀어보니 생각보다 간단히 풀 수 있었다. 여기서 주의할 점은 룩업 테이블을 활용해야 편하다는 점이다. 처음에는 count 전역 변수를 통해 큐에 좌표를 넣어줄 때마다 count 값을 1씩 증가시키는 방식으로 풀려고 했으나 값이 예제 출력값보다 크게 나왔다. 파이썬 튜터를 통해 이해할 수 있었는데, now의 다음 좌표(올라가거나 내려가거나)로 가지 못하면 count 값을 증가시키면 안되는데, 다음 값을 큐에 넣지 않아도 count 값을 증가시켜버린 탓이었다. 룩업테이블을 활용하여 다음 좌표를 큐에 넣어줄 때 현재 좌표에 저장된 값에 1을 더한 값으로 방문처리 해주었더니 문제를 해결할 수 있었다.

다음 좌표가 이미 방문처리 되어서 방문하지 못하는데 count하게 된다.

 

'Baekjoon > DFS와 BFS' 카테고리의 다른 글

[백준] 11725 트리의 부모 찾기 (실버2) / DFS  (0) 2023.04.26
[백준] 4963 섬의 개수 (실버2) / DFS, BFS  (0) 2023.04.26
[백준] 2644 촌수계산 (실버2) / DFS, BFS (feat. 파이썬튜터)  (0) 2023.04.25
[백준] 2583 영역 구하기 (실버1) / BFS  (0) 2023.04.23
[백준] 1697 숨바꼭질 (실버1) / BFS  (0) 2023.04.21
'Baekjoon/DFS와 BFS' 카테고리의 다른 글
  • [백준] 11725 트리의 부모 찾기 (실버2) / DFS
  • [백준] 4963 섬의 개수 (실버2) / DFS, BFS
  • [백준] 2644 촌수계산 (실버2) / DFS, BFS (feat. 파이썬튜터)
  • [백준] 2583 영역 구하기 (실버1) / BFS
hellosonic
hellosonic
hellosonic
꾸준함
hellosonic
전체
오늘
어제
  • 분류 전체보기 (285)
    • SSAFY (4)
    • 프로그래머스 데브코스 (26)
    • Diary (1)
    • JavaScript (20)
    • ToyPJ (13)
      • Python-Django (13)
    • CS지식 (11)
      • 자료구조 (5)
      • 개발 상식 (2)
      • 네트워크 (4)
    • Baekjoon (141)
      • IM Level (57)
      • DFS와 BFS (21)
      • 백트래킹 (21)
      • DP (3)
      • 이분탐색 (4)
      • 구현 (14)
    • Programmers (13)
      • Lv1 (4)
      • Lv2 (9)
    • SWEA (SW Expert Academy) (52)
      • D1 (5)
      • D2 (7)
      • D3 (40)
    • 이코테 (4)
    • Grammar (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기
  • 관리자

공지사항

인기 글

태그

  • 그리디
  • 구현
  • 프로그래머스
  • SWEA/D3
  • 백준 2999
  • 프론트엔드 데브코스
  • 파이썬 2529
  • SWEA D3
  • 프로그래머스 데브코스
  • javascript ux
  • 리액트 todolist
  • 파이썬 11478
  • 이코테
  • 국비지원교육
  • 백준
  • 백준 5212
  • 파이썬 1946
  • 자바스크립트 기본기
  • SWEA 파이썬
  • SWEA
  • SWEA D2
  • JS
  • 코딩부트캠프
  • 백준 1157
  • 백준 14891
  • 파이썬 1269
  • 파이썬
  • 백준 18870
  • 자바스크립트
  • 파이썬 1436

최근 댓글

최근 글

hELLO · Designed By 정상우.
hellosonic
[백준] 5014 스타트링크 (실버1) / BFS
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.