알고리즘/너비 우선 탐색(bfs)

7562-백준-나이트의 이동

2023. 2. 6. 00:11
목차
  1. 1. 문제 출처
  2. 2. 풀이
  3.  

1. 문제 출처

https://www.acmicpc.net/problem/7562

 

7562번: 나이트의 이동

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

www.acmicpc.net

2. 풀이

# 테스트 케이스 개수 받기
test_case_num = int(input())

# 나이트 8방향으로 이동 시 바뀌는 좌표 크기  
# 원점이 좌측 상단 꼭지점이고 오른쪽, 아래쪽으로 갈 때 마다
# 1 씩 좌표가 늘어나고 그 반대는 1씩 줄어 든다

# x좌표 변화량 리스트
# x 좌표 변화량 리스트가 4인 이유는 
# 원래 [-2,-1,1,2,-2,-1,1,2]  인데 -2,-1,1,2 반복이기 때문에 다음과 같이 했다.
dx = [-2,-1,1,2] 
# x좌표 변화량 리스트
dy = [-1,-2,-2,-1,1,2,2,1]

# 결과 값 저장하는 리스트
results = []

# test_case_num 만큼 반복
for _ in range(test_case_num):
    # 체스판 길이, 시작 좌표 , 목표좌표를 받는다.
    board_w = int(input())
    start = list(map(int,input().split()))
    end = list(map(int,input().split()))
    
    # 시작과 끝이 같다면 이동하지 않으므로 0을 추가하고 다음 케이스로 넘어간다.
    if start == end :
        results.append(0)
        pass
    else:
        # queue에 시작점 좌표를 추가 한다.
        queue = [[start[0],start[1]]]
        # 몇 번 째에 방문 하였는지 알기 위한 2차원 리스트 선언 및 -1로 초기화
        visited = [[-1 for _ in range(board_w)] for _ in range(board_w)]
        # 시작점은 처음 방문 하는 곳 이므로 0으로 초기화 한다.
        visited[start[0]][start[1]] =  0
    
    # queue가 empty 될 때 까지 반복한다.
    while queue:
        # queue는 FIFO(선입선출) 이므로 pop(0)로 제일 처음에 넣은 값은 빼서 가지고 온다.
        start = queue.pop(0)
        x = start[0]
        y = start[1]
        
        # 8방향 으로 이동한 좌표를 구한다.
        for i in range(8):
            move_x = x + dx[i%4]
            move_y = y + dy[i]
            # 이동한 좌표가 목표 좌표이면 results에 결과를 저장 후 queue를 비운다
            # 그 후 for i in range(8): 문을 break으로 나오면 queue가 clear 되었기 때문에 while문 반복이 종료된다.
            if (move_x == end[0]) & (move_y == end[1]):
                results.append(visited[x][y]+1)
                queue.clear()
                break
            
            # 만약 움직인 좌표가 체스판을 내에 존재하고(is_in_boar & visited[move_x][move_y] == -1   같이 쓰면 indexError가 발생 할 수 있다.)
            is_in_board = (0 <= move_x < board_w) & (0 <= move_y < board_w)
            if is_in_board: 
                # 방문하지 않은 좌표일 경우
                if (visited[move_x][move_y] == -1):
                    # 해당 좌표를 queue에 저장
                    queue.append([move_x,move_y])
                    # 해당 좌표의 최단 방문 횟수 저장
                    visited[move_x][move_y] = visited[x][y] + 1
                
for result in results:
    print(result)

 

원래는 collections를 사용해서 하려고 했으나 리스트로 충분히 가능하여 사용하지 않았다.  

'알고리즘 > 너비 우선 탐색(bfs)' 카테고리의 다른 글

16234-백준-인구이동  (0) 2023.02.23
18405-백준-경쟁적 전염  (0) 2023.02.18
18352-백준-특정 거리의 도시 찾기  (0) 2023.02.17
14502 - 백준 - 연구소  (0) 2023.02.15
9205-백준-맥주 마시면서 걸어가기  (0) 2023.02.07
  • 1. 문제 출처
  • 2. 풀이
  •  
'알고리즘/너비 우선 탐색(bfs)' 카테고리의 다른 글
  • 18405-백준-경쟁적 전염
  • 18352-백준-특정 거리의 도시 찾기
  • 14502 - 백준 - 연구소
  • 9205-백준-맥주 마시면서 걸어가기
easysheep
easysheep
easysheep
나의 개발자 일기
easysheep
전체
오늘
어제
  • 분류 전체보기 (95)
    • 파이썬 (7)
      • 자료형 (0)
      • matplotlib (2)
      • Tensorflow (1)
      • Selenium (1)
      • Numpy (2)
      • Pandas (1)
    • 장난감 프로젝트 (3)
    • AI_수학 (0)
      • 통계 (0)
    • 알고리즘 (63)
      • 브루트 포스 (3)
      • 그리드 알고리즘 (5)
      • 너비 우선 탐색(bfs) (12)
      • 깊이 우선 탐색(DFS) (1)
      • 최단 경로 구하기(플로이드 워셜) (1)
      • 동적 계획법(Dynamic Programming) (8)
      • Dijkstra algorithm(데이크스트라 알.. (6)
    • Backend (1)
      • Django (1)
    • 딥러닝 (1)
      • Regression(회귀) (0)
    • 머신러닝 (3)
      • Daycon (1)
      • 직접 구현 (1)
    • AWS (3)
    • DB (2)
      • MongoDB (2)
    • kubernetes (3)
    • Docker (4)
    • Stress Test Toll (0)
      • Jmeter (0)
      • nGrinder (0)
    • Ubuntu (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • ubuntu
  • matplotlib
  • 2*n 타일링
  • dynamic programming
  • ML
  • grafana
  • heap
  • 백준
  • error: version in "./docker-compose.yaml" is unsupported.
  • 데이크스트라
  • 머신 러닝
  • Docker
  • BFS
  • error
  • Cannot stat file /proc/528/fd/0: Permission denied
  • 너비 우선 탐색
  • gradio
  • 우분투에 헬름 설치
  • 파이썬
  • Python
  • 헬름 설치
  • validate service connection
  • Mac
  • 알고리즘
  • mysql
  • Numpy
  • helm
  • aws
  • 문자열
  • Bind Mounts

최근 댓글

최근 글

hELLO · Designed By 정상우.
easysheep
7562-백준-나이트의 이동
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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