N

https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr BFS 알고리즘. 처음 풀 때는 DFS를 사용했지만, 런타임 에러 즉, 콜스택이 초과되기 때문에 BFS를 사용해야 한다. 각 좌표마다 시작하는 방향에 따라 사이클의 여부가 달라지기 때문에, 3차원 배열을 이용해 visited를 처리했다. 우선 이중 for문으로 grid를 순회한다. 순회를 하면서 각 좌표마다 4방향으로 탐색을 진행한다..

https://leetcode.com/problems/rotting-oranges/ Rotting Oranges - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com BFS 활용. m x n 크기의 grid를 BFS 전에 한번 훑어준다. grid를 순회하면서 멀쩡한 오렌지(grid[i][j] === 1)가 있으면 orange++을 한다. 그렇지 않고 썩은 오렌지(grid[i][j] === 2)가 있다면 queue에 해당 좌표를 넣어준다. 한번 순회가 끝나고, ora..

https://leetcode.com/problems/max-area-of-island/ Max Area of Island - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com BFS 탐색 이용. m x n 크기의 visited 배열을 false로 초기화. 4방향 탐색을 위한 direct 배열도 선언. answer = 탐색한 area 중 가장 큰 값을 저장한다. bfs 함수는 x, y 값을 매개 변수로 받으며, 이 값을 통해 인접한 4방향 중 1로 된 영역의 크기를..

https://leetcode.com/problems/flood-fill/ Flood Fill - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com BFS 알고리즘. m x n 크기의 visited 배열을 선언하여 false로 초기화. 4 방향을 탐색하기 위한 direct 배열 또한 선언. color는 image[sr][sc]에 해당하는 숫자로, 탐색을 할 때 해당 숫자와 같으면 newColor로 바꾼다. image[sr][sc] = newColor로 하고, que..

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/ Populating Next Right Pointers in Each Node - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com BFS를 이용. BFS에 이용할 queue와 같은 레벨에 있는 노드를 담을 stack을 빈 배열로 선언. answer = root로 정의. 또 다른 pointer를 root로 지정하고, count는 현재..

https://leetcode.com/problems/path-with-minimum-effort/ Path With Minimum Effort - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 우선순위큐로를 이용한 풀이. MinHeap으로 우선순위 큐를 구현. BFS 방식과 비슷하게 PriorityQueue에 방문할 좌표와 minimum effort를 넣으면 된다. pq에 push하면 알아서 minHeap으로 정렬해주기 때문에 방문할 좌표와 방문 여부를 확인해..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr BFS 풀이. countDiffer()함수. 인자로 받아온 word와 target의 다른 문자가 1개인지 확인하는 함수. for문으로 word의 길이만큼 반복하면서, 문자가 몇개나 다른지 count로 확인한다. 만약 count === 1이라면 true를, 아니라면 false를 리턴한다. solutino() 함수. 정답을..

https://programmers.co.kr/learn/courses/30/lessons/86971?language=cpp 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr bfs를 활용한 문제 풀이. 우선 주어진 wires 벡터로 그래프를 그려 주도록 하자. 이후 한 노드를 선택해 연결 되어 있는 노드를 끊고 BFS 탐색을 진행하여 끊은 노드의 개수를 구하면 된다. 이때, n * n 크기의 visited 벡터를 만들어, 이미 끊었던 간선을 다시 끊는 일이 없도록 가지를 친다. bfs() 함수에 그려 놓았던 그래프와 n, 현..