leebaek

문제 첫번째 칸에서 마지막 칸까지 가는 최단 경로의 길이를 구하는 문제 문제해결 bfs를 통해 1이 적힌 칸의 개수를 찾는 것은 쉬웠는데, 최단 경로를 어떤식으로 구해야하는지 감이 안왔음 다른 분이 작성하신 코드를 보고 '아!!!!' 했음 일단, 각 칸에 첫번째 칸부터 해당위치의 칸까지의 길이를 저장할 cnt배열을 만들어야함 (-첫번째 칸은 길이가 1 임) -(0, 0) 칸의 상하좌우에 길이 있는지 확인 -(1, 0)에 길이 있다면 방문표시 & cnt 배열 (1, 0)에 cnt[0][0]값 + 1 을 넣어줌 -(1, 0)에 길이 있다면 방문표시 & cnt 배열 (0, 1)에 cnt[0][0]값 + 1 을 넣어줌 -마지막 칸에 도착하면 bfs 종료 ( 난 Q가 빌때까지 했음 ) -마지막 칸의 cnt배열 값..

문제 도화지에 그려진 그림의 개수와 그림의 최대 넓이값을 출력하는 문제 문제해결 알고리즘 BFS(너비우선탐색) 방법 사용 1. 그림판에서 그림이 그려지는 시작 부분을 찾음 ( 그림의 개수 +1 ) 2. 찾은 부분을 큐에 넣고 상하좌우 확인/ 큐가 빌 때까지 반복 ( 그림의 넓이 + 1 ) 3. 그림의 최대 넓이와 비교함 #include using namespace std; #define X first #define Y second int board[502][502]; bool vis[502][502]; int n, m; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main(void) { ios::sync_with_stdio(0); cin.tie(..

바킹독의 실전 알고리즘 0x09강 정리 BFS(Breadth First Search) : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 순서 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 '3번'을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 4. 큐가 빌 때까지 '2번'을 반복 - 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N) 예시코드 #include using namespace std; #define X first; // pair의 first, second를 쉽게 쓰기 위해 X, Y 로 정의 #def..