본문 바로가기
반응형

BFS13

[프로그래머스] Lv2. 게임 맵 최단거리 - 자바(JAVA) 문제 설명ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다.캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.첫 번째 방법은 11개의 칸.. 2025. 5. 28.
[프로그래머스] Lv2. 전력망을 둘로 나누기 - 자바(JAVA) 문제 설명n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절댓값)를 return 하도록 solution 함수를 완성해 주세요. 제한사항n은 2 이상 100 이하인 자연수입니다. wires는 길이가 n-1인 정수형 2차원 배열입니다.wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v.. 2025. 5. 23.
[리트코드] Medium 236. Lowest Common Ancestor of a Binary Tree - 자바(JAVA) 문제 설명이진 트리가 주어졌을 때, 주어진 두 노드의 최저 공통 조상(LCA, Lowest Common Ancestor)을 찾아라.Wikipedia의 LCA 정의에 따르면:“최저 공통 조상(LCA)은 트리 T에서 두 노드 p와 q 사이에 정의되며, p와 q 모두의 자손인 노드 중에서 가장 낮은(가장 깊은) 노드를 의미한다. 여기서 노드는 자기 자신을 자손으로 간주할 수 있다.” 제한사항 트리의 노드 수는 [2, 105] 범위입니다.-10⁹ 모든 Node.val은 고유합니다.p != qp와 q는 트리에 존재합니다. 문제 파악두 노드 p, q의 최저 공통 조상(LCA)을 찾는 문제이다.LCA는 p와 q가 자손인 노드 중 가장 아래에 있는 노드이다. (자기 자신도 자손으로 친다.) 접근 방법재귀 탐색(DFS).. 2025. 5. 23.
[리트코드] Easy 104. Maximum Depth of Binary Tree - 자바(JAVA) 문제 설명이진 트리의 루트 노드가 주어졌을 때, 해당 트리의 최대 깊이를 반환하세요.이진 트리의 최대 깊이는 루트 노드에서 가장 먼 리프 노드까지의 경로에 포함된 노드 수를 의미합니다. 제한사항트리의 노드 수는 0 이상 10,000 이하의 범위에 있습니다.-100 문제 파악이진 트리의 최대 깊이(depth)를 구하는 문제이다.최대 깊이는 루트 노드에서 가장 깊은 리프 노드까지의 노드의 수를 의미한다. 접근 방법재귀 호출 방식으로 최대 깊이를 구한다.왼쪽, 오른쪽 서브트리의 최대 깊이를 구해서 둘 중 더 큰 값을 선택해 1을 더한다. 코드 구현/** * Definition for a binary tree node. * public class TreeNode { * int val; * Tree.. 2025. 5. 20.
[알고리즘] 그래프 문제를 위한 DFS, BFS 템플릿(구현 코드) - 자바(JAVA) 코딩 테스트 준비를 위해 알고리즘을 배우며 그래프 파트를 공부하다 보니DFS, BFS 기본 템플릿을 모르면 문제를 손도 못 대겠더라구요...!그래서 이건 무조건 외워야겠다 싶어서 따로 정리했습니다. 이 템플릿만 알아도 그래프 문제 풀이의 시작점은 잡을 수 있습니다.저도 여러 번 직접 쳐보면서 외웠습니다! 1. DFS (깊이 우선 탐색)static boolean[] visited;public static void dfs(int node, ArrayList[] graph) { visited[node] = true; // 방문 표시 for (int next : graph[node]) { if (!visited[next]) { dfs(next, graph); // 아직.. 2025. 5. 18.
[프로그래머스] Lv2. 미로탈출 - 자바(JAVA) 문제 설명1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는 데 걸리는 시간을 구하려 합니다. 미로를 나타낸 문자열 배열 maps가 매개.. 2025. 5. 18.
반응형

티스토리툴바