BFS

난이도 : 골드 4유형 : BFS / DFS / DP링크 : https://www.acmicpc.net/problem/12869구현 시간 : 30분     문제 풀이 이 문제는 BFS / DFS 알고리즘의 유형으로, 뮤탈리스크는 한 번의 공격에서 세 개의 SCV에 각각 9, 3, 1의 피해를 줄 수 있으며, 세 개의 공격 순서를 자유롭게 선택할 수 있습니다.즉, 모든 가능한 공격 순서를 고려하여 최소 공격 횟수를 찾아야 하는 문제입니다. 얼핏 보면 SCV 체력을 내림차순으로 정렬하고, 9 -> 3 -> 1 순서로 공격하면 쉽게 해결할 수 있지 않나? 싶지만아래 예제를 보면 그리디하게 문제를 해결할 수 없다는 것을 알 수 있습니다.SCV의 체력이 (12 , 10, 4)일 때첫번째 공격 -> 1, 3, 2 ..

난이도 : Level 3유형 : BFS / 구현구현 시간 : 1시간링크 : https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   문제 설명로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌..

난이도 : Level 4유형 : BFS / 우선순위 큐구현 시간 : 1시간 20분 (못품)링크: https://school.programmers.co.kr/learn/courses/30/lessons/62050 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr       문제풀이위 문제는 Summer/Winter Coding(2019) 기출 문제로 처음으로 풀어보는 레벨 4의 문제였다. 확실히 비슷한 BFS 문제인 경주로 건설보다는 어렵게 느껴졌다. 1시간동안 고민하며 구현한 결과 Node에 좌표 정보와 비용을 저장하고 우선순위 큐를 사용하여 BFS를 구현하는 것에는 성공했지만, 우선순위 큐에 추가할 No..

너비 우선 탐색(BFS, Breadth-First Search)BFS는 그래프 탐색 알고리즘 중 하나로, 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘이다. BFS는 최단 경로를 찾는 알고리즘으로도 많이 쓰이곤 하는데, 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문이다. 쉽게 말해 문제에 대한 답이 많은 경우 너비 우선 탐색은 이 답 중에서도 가장 가까운 답을 찾을 때 유용하다. BFS는 주로 FIFO(선입선출) 방식인 큐 자료구조를 사용하여 구현한다.인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.(DFS는 이와 반대로 스택을 통해 구현한다.) BFS 작동 원..

난이도 : 골드 5유형 : BFS / 큐링크 : https://www.acmicpc.net/problem/7569구현 시간 : 1시간       문제풀이토마토 박스를 3차원 배열에 저장한다.1번 과정에서 빈칸의 개수, 익은 토마토의 개수를 저장한다.(총 배열의 크기 - 빈칸의 개수) 가 익은 토마토의 개수와 같다면 0 을 출력하고 종료한다.익은 토마토가 있는 좌표를 Queue에 저장한다.Queue 가 비어있지 않을때까지 반복문 시작Queue의 현재 size 를 저장하고, size 만큼 for문을 돌린다. (BFS 탐색의 Depth를 기준으로 하루가 지남을 판별하기 위함)Queue에서 poll한 익은 토마토의 위치 기준 상하좌우아래위 6방향으로 탐색한다.만약 탐색 위치가 박스 위치를 벗어나면, 다음 방향으..

난이도 : Level 3유형 : BFS / 큐구현 시간 : 1시간 (못품)링크: https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr      문제풀이위 문제는 2020 카카오 인턴십 코딩 테스트에 출제된 문제로 현재까지 풀어본 BFS 문제와는 다르게 생각이 많이 필요했다.최단 경로를 구한다고 하더라도 그 경로가 가장 저렴한 비용이 들지 않기 때문에 최소 비용을 저장해서 문제를 구현했다.  x, y 좌표 및 방향 정보를 저장하는 cost 배열을 사용해서 시작점을 제외한 모든 데이터를 최대값으로 저..

난이도 : Level 2유형 : BFS / 큐구현 시간 : 30분링크 :https://school.programmers.co.kr/learn/courses/30/lessons/159993  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr      문제풀이위 문제는 BFS 탐색 알고리즘을 사용하여 최단 경로를 찾는 문제이다. 앞서 백준을 통해 BFS / DFS 문제를 많이 연습해두었기에 알고리즘을 구현하는 것은 오래 걸리지 않았지만 BFS 를 총 2번 실행하는 과정에서 데이터 초기화에 문제를 겪었다. 시작점, 레버, 도착지의 위치 정보 저장시작점 -> 레버까지 최단 경로를 BFS 를 통해 구함만약 레버까지..