BFS

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • (시작점이 여러 개인) BFS - 처음 상해있는 귤들을 전부 시작점으로 잡아 그 위치들을 큐에 추가하고, BFS는 한 번 수행한다. ▷ 시간 복잡도 : O(N^2) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 6..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 다익스트라 (397ms, 29MB) 연산횟수를 저장하는 1차원 int형 배열을 생성해 초기값을 큰 값으로 저장해두고, 시작점 N은 거리를 0으로 설정한다. 연산횟수가 적은 순으로 오름차순 정렬하는 우선순위 큐에 4가지 경우(현재 숫자에서 1을 뺀 경우, 1을 더한 경우, 2로 나눠 떨어질 경우 2로 나눈 경우, 3으로 나눠 떨어질 경우 3으로 나눈 경우)를 추가한다. 그리고 이동했을 때의 연산횟수와 현재 위치에서 1초 지난 값을 비교해 연산횟수 배열을 둘 중 더 값이 작은 값으..

📖 문제 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 💡 풀이 방식 • BFS + 시뮬레이션 필요 자료구조 - 판 정보 저장할 2차원 int형 배열 - 2차원 boolean형 방문 표시 배열 - 남아있는 치즈조각이 놓여 있는 칸의 개수 저장하는 리스트 판에 치즈조각이 존재하는 동안 아래 과정을 반복한다. ① 방문 표시 배열을 초기화한다. ② (0,0)에서부터 BFS를 수행하며 경계선에 있는 모서리 칸들 = 공기(0)인 칸을 모두 방문 표시하러 간다. ((0,0)이 확실하게 공기인 칸이니까) → 이동 가능 조건 : 방문한 적 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 가중치가 동일한 그래프에서의 BFS 각 사람마다 BFS를 수행해 가장 가까운 쉘터를 구하도록 했다. ⇨ 시간 복잡도 : O(hN^2) 1. 격자를 입력받으면서, 사람(2)의 위치도 리스트에 저장해둔다. 2. 사람 위치가 저장된 리스트를 돌면서, 각 사람이 비를 피할 수 있는 공간 3까지 가는 최단 거리를 bfs를 통해 구한다. 방문 배열을 매번 초기화해줘야 한다. 사람 위치(2)에서 bfs를 진행하며 3까지 bfs를 수행한다. (=최단 거리) 큐에는 (방문할 행, 열, 거리 값..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 + BFS 사용 자료구조 [백트래킹용] - 도시 위치와 인덱스 저장할 int형 2차원 배열 ⇨ int[][] cities = new int[n*n + 1][2]; - 뽑은 도시 저장할 int형 리스트 [BFS용] - dx/dy 배열 - 방문 표시 배열 - 최댓값 도시 정보를 입력받을 때 해당 도시의 행,열 값과 인덱스를 도시 정보 배열 cities에 저장한다. 백트래킹을 통해 도시 정보 배열을 돌며 이 중 도시 k개를 뽑는다. 만약 k개를 뽑지 않았다면, 해당 인덱스의..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • BFS 1. 빙하에 둘러쌓여 있지 않은 물들을 구해야 한다. ▷ 매번 (0,0)에서 BFS를 수행한다. 2. 완전탐색을 통해 주변에 빙하에 둘러쌓여 있지 않은 물이 있는 빙하들을 찾아 녹인다. 3. 과정 1,2를 격자 내에 빙하가 존재하지 않을 때까지 실행하며 걸리는 시간과 마지막으로 녹은 빙하의 크기를 갱신한다. ▷ 완전탐색 통해 확인 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 + BFS 필요 자료구조 - 돌 위치 저장용 리스트 rockList ⭐ - 고른 돌 목록 1차원 int형 배열 (dfs용) - 방문 표시 배열 (bfs용) - 시작점 위치 1차원 int형 배열 startPos ⭐ 1. 격자를 입력받으면서, 돌이 있는 위치를 rockList 리스트에 저장한다. 2. startPos 배열에 K번 시작점 위치를 저장한다. 3. M개를 뽑는 dfs를 수행한다. - 종료 조건 : m개 뽑았을 때 3-1) 돌을 제거한다. 3-2) 시작점에서부터 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • BFS 1) 현재 위치에서 이동 가능한 칸 전부 찾기 2) 도달 가능한 칸 中 우선순위가 가장 높은 칸 위치 구하기 - 도달 가능한 칸 있다면, 현재 칸 위치를 해당 위치로 옮기기 - 도달 가능한 칸 없다면, 움직이기 종료 시작 위치에서 상하좌우에 본인보다 작은 값이 없다면, 이동할 수 없으므로 종료한다. 하지만 본인보다 작은 값이 존재한다면, 아래와 같이 진행한다. 1) bfs를 통해 배열을 탐색하며 방문 가능한(=격자 범위 내에 있고, 방문한 적 없고, 기준 점의 값보다 작..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • BFS 필요 자료구조 - dx/dy 배열 - 2차원 char형 배열 (1차원 String형 배열 maps 저장용) - 2차원 boolean형 배열 (방문 표시용) - 2차원 int형 배열 start (시작 위치 저장용 배열) - 2차원 int형 배열 lever (레버 위치 저장용 배열) 1. 1차원 String형 배열을 2차원 char형 배열로 저장한다. 저장하면서 S가 나타났을 때는 해당 좌표를 시작 위치에 저장하고, E가 나타났을 때는 해당 좌표를 레버 위치에 저장한다. 2. B..