BOJ 17485번 진우의 달 여행(Large) 문제 자바(java) 풀이 랭크 : 골드5 백준 17485번 진우의 달 여행(Large) 문제정리 지구와 우주 사이는 NxM 행렬로 나타낼 수 있다. 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다. 지구->달로 가는 경우 왼쪽 아래, 아래, 오른쪽 아래 3가지의 방향으로만 이동 가능하다. 같은 방향으로 두번 연속 움직일 수 없다. 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙해야한다. 달에 도달하기 위해 필요한 연료의 최소값을 계산하자. 문제풀이 데이터의 크기가 크기 때문에 Dynamic Programming(DP) 기법을 적용해서 풀어야 합니다. dfs로 풀게 되면 시간초과가 나오게 됩니다. 3차원 배열을 ..

BOJ 3584번 가장 가까운 공통 조상 자바(java) 풀이 랭크 : 골드4 백준 온라인 저지(BOJ) 3584번 가장 가까운 공통 조상 문제 자바 풀이 백준 3584번 가장 가까운 공통 조상 문제정리 테스트 케이스와 트리를 구성하는 노드의 수 N이 주어진다. 트리를 구성하는 간선 정보가 주어질 때, A B가 주어지면 A가 B의 부모라는 뜻이다. 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어진다. 이때 두 노드의 가장 가까운 공통 조상을 출력한다. 문제풀이 이 문제는 LCA(Lowest Common Ancestor)문제 입니다. LCA를 검색하면 정리된 많은 자료들을 볼 수 있습니다. 만약 트리의 루트가 어떠한 노드로 고정되어 있다면 dfs를 통해 탐색할 수 있습니다. 하지만 이 문제는 루..

BOJ 11437번 LCA 자바(java) 풀이 랭크 : 골드3 백준 온라인 저지(BOJ) 11437번 LCA 문제 자바 풀이 백준 11437번 LCA 문제정리 1~N번으로 번호가 매겨진 정점들이 주어진다. 루트는 1번이다. 가장 가까운 공통 조상을 알고 싶은 m개의 쌍이 주어진다. n-1개의 트리 상에서 두 정점의 연결 정보가 주어진다. 이때 A B라고 주어질때 A가 부모라는 보장이 없다. 문제풀이 이 문제는 LCA(Lowest Common Ancestor)문제 입니다. LCA를 검색하면 정리된 많은 자료들을 볼 수 있습니다. 이 문제는 depth를 모두 구하고 부모와 자식간의 관계를 구하여 트리를 만든 다음에 구하고자 하는 정점의 depth를 맞춰준다음 같은 노드가 될 때 까지 부모를 타고 하나씩 올..

BOJ 1260번 DFS BFS 자바(java) 풀이 랭크 : 실버1 백준 온라인 저지(BOJ) 1260 DFS BFS 문제 자바 풀이 백준 1260 DFS BFS 문제 문제정리 N M V(정점의 개수, 간선의 수, 시작할 정점 번호) 연결 정보들이 주어진다. 그래프 정보들을 가지고 dfs와 bfs로 순회하여 순서대로 출력하기 문제풀이 이 문제는 정점의 연결 상태를 적절한 자료형으로 저장하여 그래프를 탐색하는 문제입니다. 저는 그래프의 연결 상태를 인접 그래프(adjancy graph)형태로 저장하여 탐색하였습니다. 인접 행렬 다음과 같은 인접 행렬가 주어졌습니다. 무엇을 나타내는 걸까요?? 010 101 010 adj[i][j] = 1 이라면 점 i와 j는 연결되어 있다. 0이면 연결되어 있지 않다. ..

BOJ 2178 미로 탐색 자바(java) 풀이 랭크 : 실버1 백준 온라인 저지(BOJ) 2178 미로 탐색 문제 자바 풀이 백준 2178 미로 탐색 문제 문제 정리 '1'은 이동할 수 있고 '0'은 이동할 수 없는 칸이다. (1,1)에서 출발한다. (n,m)으로 이동할때 지나야 하는 최소의 칸 수를 구해여라 시작 위치와 도착위치도 포함하여 칸을 센다. 문제 풀이 이 문제는 모든 경우를 따져봐야 합니다. 즉 완전 탐색입니다. 완전 탐색을 위해서 bfs를 이용해야 합니다. dfs를 이용해서 탐색하게 되면 시간초과를 만나게 됩니다. 한쪽만 잘 못 파고 들어가게 되면 dfs 같은 경우 오래 걸릴 수 있기 때문입니다. 이 문제는 최단 거리를 구하라는 뜻과 같습니다. 최단 거리를 구..

BOJ 17484번 진우의 달 여행(Small) 자바(java) 풀이 랭크 : 실버5 백준 온라인 저지(BOJ) 17484번 진우의 달 여행(Small) 문제 자바 풀이 백준 17484번 진우의 달 여행(Small) 문제 정리 지구와 우주 사이는 NxM 행렬로 나타낼 수 있다. 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다. 지구->달로 가는 경우 왼쪽 아래, 아래, 오른쪽 아래 3가지의 방향으로만 이동 가능하다. 같은 방향으로 두번 연속 움직일 수 없다. 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙해야한다. 달에 도달하기 위해 필요한 연료의 최소값을 계산하자. 문제 풀이 이 문제는 dfs 함수만 구현할 수 있으면 풀 수 있는 문제입니다. 입력을 받아 2..