본문 바로가기

BFS34

[C++/PGS] Lv.3 : 양과 늑대 (DFS) https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr프로그래머스 레벨 3.꽤나 까다로웠던 문제 👿탐색 시 조건이 있으므로, dfs 백트래킹을 적용한다.근데 백트래킹은.. 안해도 된다 (단방향 그래프이고, 방문 체크가 없음) DFS에 현재 인덱스, 양의 수, 늑대의 수, 그리고 현재 위치에서 갈 수 있는 다음 노드 목록을 전달하면연결된 다음 노드를 방문하고조건에 맞지 않으면 재귀를 중단하고 반환한다. bfs로 푸는 방법도 있던데, 그건 아래의 링크를 참고하면 될 듯하다.너비우선 탐색으로 풀 때는 .. 2025. 4. 15.
[Javascript/PGS] Lv.2 : 석유 시추 (PCCP 기출문제 2번) https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr프로그래머스 레벨 2.BFS 응용 문제이다너비우선탐색으로 석유칸 수를 카운트하고, 어떤 열에서 뽑을 수 있는건지 Map에 누적한다!코드가 길긴 했지만 크게 어려운 문제는 아니었다고 생각🤓  나의 풀이let Land;let n; let m;let visited;let dx = [0,1,0,-1];let dy = [-1,0,1,0];let columnMap = new Map();const saveColumns=(columns, count)=>{ .. 2025. 3. 26.
[Javascript/PGS] Lv.3 : 여행경로 https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=javascript 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr프로그래머스 레벨3DFS 유형 문제이고, 예전에 CPP로 풀었는데 js로 다시 풀어보았다. 한 경로로 끝까지 탐색해야하므로 깊이우선 탐색을 진행,만약 끝까지 진행하지 못한다면 백트래킹이 필요하다!(pop & visited false 처리)  나의 풀이let answer = [];let isAnswer = false;let visited = new Array(10001).fill(false);let Tickets.. 2025. 3. 24.
[Javascript/PGS] Lv.3 : 부대복귀 https://school.programmers.co.kr/learn/courses/30/lessons/132266# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr프로그래머스 레벨 3.최단거리를 보고 BFS 문제겠거니 추측하였다.보통 좌표(?)가 주어지는 문제는 너비우선탐색으로 최단거리를 찾기 때문에,,ㅎㅎ  1. 첫 시도 - 테스트케이스 11번~15번 시간초과   왜 초과가 났나 했는데 😢JS로 알고리즘 푸는게 익숙하지 않아서 bfs를 반복문에 넣어버린 탓이었다.바꾸는 김에 다른 코드들도 조금씩 더 짧고 효율적으로 변경해보았다.(Map.get 으로 데이터 유무 확인 -> Map.has로 확인하는 등.. 2025. 3. 20.
[Javascript/PGS] Lv.3 : 아이템 줍기(BFS) https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 프로그래머스 레벨 3 문제이다처음에 일부 테케가 계속 틀려서 삽질했었는데알고보니 map 변수를 채우는 게 문제였다.... (이거 하나때문에 몇 시간을 앓음) js에서는 배열 값을 직접 바꿀때 중복이 되면 뭔가 오류가 생기나보다중복, 덮어쓰기 최대한 없도록 짜기! Main Idea => 맵을 두 배로 늘려서, ㄷ자로 우회해야하는데 직행하게 되는 부분이 없도록 함그리고 최단거리를 찾는 문제이니, BFS로 푼다!  나의 풀이let dx = [0, 1.. 2025. 2. 17.
[C++/PGS] Lv.2 : 전력망을 둘로 나누기 (완전탐색/bfs/dfs) https://school.programmers.co.kr/learn/courses/30/lessons/86971 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 2 이상 100 이하인 자연수입니다. wires는 길이가 n-1인.. 2023. 5. 26.
728x90
반응형