Coding Test/Problem Solving
-
격자 문제를 이해하기 위한 기본 코드 (Python)Coding Test/Problem Solving 2022. 8. 26. 21:08
완전탐색 문제에서 자주 등장하는 방향 탐색 1. 한 칸씩 움직인다는 가정 하에, 방향을 설정한다. dx = [1, 1, 0, -1, -1, -1, 0, 1] dy = [0, 1, 1, 1, 0, -1, -1, -1] 방향은 시계 방향 순서이다. → ↘ ↓ ↙ ← ↖ ↑ ↗ → 좌표는 1사분면을 기준으로 오른쪽으로 갈수록 x값이 증가, 위로 갈수록 y값이 증가한다. 그러나 격자의 경우 오른쪽으로 갈수록 x값이 증가, 아래로 갈수록 y값이 증가한다. 2. (0, 0)부터 (n, n)까지 움직일 2중 for문을 작성한다. for i in range(1, n+1): for j in range(1, n+1): check_direction(i, j) # 8가지 방향 탐색 함수 python의 for문은 n+1까지 범..
-
BFS(너비우선탐색)는 있냐? 없냐? 만 기억하면 된다! (Python)Coding Test/Problem Solving 2022. 7. 18. 21:48
Problem BFS를 사용할 때에 가중치가 같다면 반드시 최솟값이 보장된다는 것이 이해가 안 갔다. 미로를 탐색한다고 했을 때 막다른 길이 있을 수도 있고 길이 여러 갈래로 나뉘어져있을 수도 있는데 이를 어떻게 확신할 수 있는 지 도무지 이해가 가지 않았다. Searching 백준에서 BFS 중 가장 기본 문제로 유명한 미로 탐색 의 이미지를 가져와봤다. 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 아래와 같은 미로에서 출발점으로부터 도착점까지의 최솟값을 구하는 문제다. 여기서 2가지만 기억하자. 인접한 좌표 중에서 벽이 아닌, 지나갈..