ABC 332 D번 복기 - 행,열 바꿔서 다른 2차원 배열과 똑같이 만드는법(BFS가 된다고?)

1. 문제 D - Swapping Puzzle (atcoder.jp) D - Swapping Puzzle AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 비슷한 문제들이 그리디로 풀려가지고... 숫자 다르면 무조건 바꾸는 그리디인가도 생각해봤는데.. 제한이 H,W가 5 이하라서 완전탐색이 가능할 것 같다고 생각을하고, 생각까진 하더라도 완전탐색을 어떻게 해야할지.. 근데 그 전에 문제부터 제대로 못읽었던것도 문제.. Choose an integer i satisfying 1≤i≤H−1 and swap the i..

• format_list_bulleted Atcoder
• · 2023. 12. 11.
• textsms

DFS/BFS 완전정복기4 -상하좌우로 움직이지 않는 경우-

1. 문제1 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 나이트가 최소 몇번 이동하면 주어진 칸으로 이동할 수 있는지 구하는 문제 어렵게 생각할 필요 전혀 없이, 문제에서 주어지는 1번에 이동할 수 있는 경우를 모두 델타배열에 저장하여, 그것을 순회하면 된다 2. 풀이 어렵게 생각할 필요 전혀 없고 일반적인 bfs 흐름으로 가다가 상하좌우 델타배열 [[0,1],[1,0],[0,-1],[-1,0]]을 나이트가 이동할 수 있는 칸으로 바꾼 델타배..

• format_list_bulleted DFS BFS 정복기
• · 2022. 9. 7.
• textsms

BFS 알고리즘 유형별로 기본 틀 정리(기초, 미로찾기, 확산)

1. 가장 기본형태 방문배열 visited 생성 빈 큐에 방문 시작할 정점 v를 넣고 v에 대한 방문처리 큐가 빌때까지 반복문 - 큐에서 정점 v를 빼고 v에 대해 할일을 수행하면서 v에 인접한 정점 w중에 방문하지 않은 w라면 다시 큐에 넣고 w에 대해 방문처리 def bfs(v,N): #시작정점 v, 마지막 정점 N #visited 생성 visited = [0] * (N+1) #큐를 생성함 q = [] q.append(v) #시작점이 들어간 큐 ### q=[v] visited[v] = 1 while q: #큐가 비어있지 않다면 탐색 v = q.pop(0) #시작점 뽑아내기 #방문한 v를 이용해 할일 print(v) #인접하고 미방문한 (in queue되지 않은) 정점 w가 있으면... for w in..

• format_list_bulleted DFS BFS 정복기
• · 2022. 8. 31.
• textsms