Coding Diary

문제 및 코드 1. 생각 // 0: 벽, 1: 벽 아님 // 생각 // 시작점부터 시작해서 상하좌우를 살피면서 1이면 거기로 가고 0이면 안 가고 // 근데 최단 경로로 가야 하니까 bfs // 구현 // 시작점을 bfs에 넣기 // bfs // 시작점과 maps를 매개변수로 받기 // bfs 위한 큐 생성 // 시작점을 큐에 넣기 // 큐가 비어있지 않을 때까지 반복 // 큐에서 하나 빼고 방문했다고 표시하고 길이 1 증가 // 큐에서 뺀 거 기준으로 상하좌우 돌기 위해 for문으로 4번 돌기 // 시작점 기준 상하좌우가 maps 안에 있으면서 1이면 해당 위치를 큐에 넣기 초반에 생각했던 걸로 이 구현 틀은 틀렸다... 2. 회고 visited 배열의 행 열을 반대로 설정했었다... 곰곰이 생각해보니..

1. 개념 주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점들을 순회하는 것을 그래프 순회라고 한다. BFS는 그래프를 순회하는 방법 중 하나이다. BFS는 시작 노드부터 출발해서 시작 노드와 인접한 것들을 모두 방문한다. 그리고 다음 노드를 방문하고, 그 노드와 인접한 것들을 모두 방문한다. 2. 예시 위와 같은 그래프를 BFS로 방문하면 다음과 같다. 방문 우선순위는 숫자 오름차순이다. 1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7 3. 특징 선입선출 탐색이다 큐 자료구조를 이용한다 시간복잡도는 O(노드 수 + 에지 수)이다. 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다 4. 코드 1) 연결리스트 만들..