[백준] 16173 점프왕 쩰리(small)

문제

쩰리가 점프 게임을 한다. 규칙은 다음과 같다.

쩰리는 정사각형 미로 내부에서만 움직일 수 있다. 미로 밖으로 나갈 경우 탈락

출발점은 항상 가장 왼쪽, 가장 위쪽 칸.

쩰리씨는 오른쪽과 아래쪽으로만 움직일 수 있다.

승리 조건은 쩰리가 가장 아래, 가장 오른쪽 칸에 도달하는 경우

젤리가 한 번에 이동할 수 있는 칸 수는 현재 위치한 칸에 쓰여져 있는 수 만큼.

입력

첫 번째 줄: 구역의 크기
두 번째 줄 ~ 마지막 줄: 게임판의 구역
게임판 승리 지점에는 -1. 나머지 칸에는 0이상 100이하의 정수

BFS: 너비 우선탐색

설명: 먼저 시작 정점을 방문한 후 해당 정점과 인접한 정점을 차례대로 탐색하는 방식
가까운 거리에 있는 정점들을 차례대로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)가 필요

알고리즘

  BFS(v):
      v를 방문했다 표시;
      큐에 정점 V 삽입;
      while(Q가 공백이 아니라면) do
          Q에서 정점 w 삭제;
          for all (w에 인접한 정점) do
              if(u가 아직 방문되지 않았다면)
                  then u를 큐에 삽입;
                       u 방문 표시;

시작 정점으로부터 거리가 가까운 정점 순서로 탐색을 진행한다는 특징

코드

12 Aug 2022

« IoC, DI, 컨테이너

스프링 컨테이너와 스프링 빈 »

homebdy Follow 개발에 이제 막 발 담근 사람. 개발에 이제 막 발 담근 사람. 개발에 이제 막 발 담근 사람. 개발에 이제 막 발 담근 사람.

Categories

[백준] 16173 점프왕 쩰리(small)

문제

입력

BFS: 너비 우선탐색

코드