고도고도
🍎🍏
고도고도
전체 방문자
7,922
오늘
2
어제
26
  • 분류 전체보기 (149) N
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (43) N
      • TIL (16)
      • Android (6)
      • Kotlin (4)
      • Flutter (9) N
      • Node.js (5)
      • Error (3) N
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (50)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (7)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

인기 글

  • [TIL] 22.03.13
    2022.03.13
    [TIL] 22.03.13
  • [문자열 / Kotlin] 2020 KAKAO⋯
    2022.03.11
    [문자열 / Kotlin] 2020 KAKAO⋯
  • [TIL] 22.03.20
    2022.03.20
    [TIL] 22.03.20
  • [퍼듀 일기] 어느덧 한 달째
    2022.03.01
    [퍼듀 일기] 어느덧 한 달째
  • [퍼듀 일기] 적응 완료
    2022.03.05
    [퍼듀 일기] 적응 완료

최근 글

  • [Flutter] ModalBottomSheet가⋯
    2022.08.09
    [Flutter] ModalBottomSheet가⋯
  • [Error / Gradle] The current⋯
    2022.08.09
    [Error / Gradle] The current⋯
  • [Flutter / Dart] What is Equa⋯
    2022.08.06
    [Flutter / Dart] What is Equa⋯
  • [Flutter] BLoC 패턴으로 자동⋯
    2022.07.26
    [Flutter] BLoC 패턴으로 자동⋯
  • [Flutter / Dart] What is Sing⋯
    2022.07.21
    [Flutter / Dart] What is Sing⋯

최근 댓글

  • 잘보고 갑니다~
    개갓세
  • 좋은 글이네요
    날인로세
  • 잘 보고 갑니다^^
    프로퍼티
hELLO · Designed By 정상우.
고도고도

🍎🍏

[DFS와 BFS] [Python / C++] 7562. 나이트의 이동.
✍️ 코테 준비/DFS, BFS

[DFS와 BFS] [Python / C++] 7562. 나이트의 이동.

2021. 4. 13. 16:07

www.acmicpc.net/problem/7562

 

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수

www.acmicpc.net

 

 

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.


해결 방법

BFS 활용 문제이다. 나이트가 이동할 수 있는 범위는 총 8개로 아래와 같다.

(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)

 

다른 BFS 문제와 동일하게 반복문을 통해 다음 이동 좌표를 구하고

범위 이내에 들어온 경우에 방문 여부를 확인하고 방문하지 않은 좌표인 경우 해당 좌표에 그 횟수를 기록해주면 된다. 

 

간단한 문제이므로 추가적인 설명은 필요 없을 것 같다.

 

파이썬으로 구현해봤다.

 

 

C++로도 구현해봤다.

 

 

 

 

저작자표시

'✍️ 코테 준비 > DFS, BFS' 카테고리의 다른 글

[BFS][Kotlin] 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기  (0) 2022.03.20
[DFS와 BFS] [Python / C++] 1260. DFS와 BFS  (0) 2021.04.18
[DFS와 BFS] [Python / C++] 1707. 이분 그래프  (0) 2021.04.14
[DFS와 BFS] [Python / C++] 7562. 나이트의 이동.  (0) 2021.04.13
[DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기.  (0) 2021.04.12
    '✍️ 코테 준비/DFS, BFS' 카테고리의 다른 글
    • [BFS][Kotlin] 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기
    • [DFS와 BFS] [Python / C++] 1260. DFS와 BFS
    • [DFS와 BFS] [Python / C++] 1707. 이분 그래프
    • [DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기.
    C++, dfs와 bfs, 백준, 파이썬
    고도고도
    고도고도
    좋아하는 것을 하자\n 스위프트 찍먹중\n 광고 없는 블로그
    댓글쓰기
    다음 글
    [DFS와 BFS] [Python / C++] 1707. 이분 그래프
    이전 글
    [DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기.
    • 이전
    • 1
    • 2
    • 3
    • 4
    • 5
    • 다음