고도고도
초록 로봇 🤖
고도고도
전체 방문자
6,070
오늘
0
어제
7
  • 분류 전체보기 (137)
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (33)
      • TIL (13)
      • Android (4)
      • Kotlin (4)
      • Flutter (5)
      • Node.js (5)
      • Error (2)
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (42)
      • Math (1)
      • Implementation (2)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (0)
      • 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)

블로그 메뉴

  • 홈
  • 깃허브

인기 글

  • 5. SingleChildScrollView, Lis⋯
    2021.08.18
  • [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
  • [투포인터 / Kotlin] BOJ 3273⋯
    2021.12.25
    [투포인터 / Kotlin] BOJ 3273⋯

최근 글

  • [Android] MVVM 패턴 적용기 - 2
    2022.05.14
    [Android] MVVM 패턴 적용기 - 2
  • [코틀린 완전정복] 공변성, 반⋯
    2022.05.02
    [코틀린 완전정복] 공변성, 반⋯
  • [코틀린 완전정복] 제네릭
    2022.04.25
    [코틀린 완전정복] 제네릭
  • [코틀린 완전정복] 여러 종류의⋯
    2022.04.23
    [코틀린 완전정복] 여러 종류의⋯
  • [코틀린 완전정복] 추상 클래스⋯
    2022.04.22
    [코틀린 완전정복] 추상 클래스⋯

최근 댓글

  • 잘보고 갑니다~
    개갓세
  • 좋은 글이네요
    날인로세
  • 잘 보고 갑니다^^
    프로퍼티
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, 백준, 파이썬
    고도고도
    고도고도
    안드로이드 개발자가 되고 싶은 컴공생
    댓글쓰기
    다음 글
    [DFS와 BFS] [Python / C++] 1707. 이분 그래프
    이전 글
    [DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기.
    • 이전
    • 1
    • ···
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • ···
    • 137
    • 다음