본문 바로가기

알고리즘78

1260번 - BFS와 DFS BFS와 DFS라는 실버 1 문제이다.문제는 아래와 같다. 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.dfs() 메서드와 bfs() 메서드를 작성하여 문제를 풀 것이다. DFS(깊이 우선 탐색) 위와 같은 그래프가 있다. dfs는 말 그대로 깊은 곳부터 먼저 탐색하는 방법이다.이렇게 1 -> 2 -> 5 -> 11로 그래프의.. 2024. 7. 19.
17070번 - 파이프 옮기기 골드 4티어 파이프옮기기 라는 문제이다.각 자세별로 아래와 같이 이동 가능하고 각 파이프가 차지하는 칸은 색칠한 곳과 같다.이때 파이프가 이동 할 수 있는 경로의 경우의 수를 구하는 문제이다.입출력은 아래와 같으며 파이프는 좌측 상단 두칸에 가로로 출발한다.1이 포함된 칸은 이용하지 못한다.그렇다면 조건은 아래와 같다는 것을 알 수 있다. 1. 파이프의 끝이 우측 하단에 도달하면 경우의 수 + 1이다.2. 다음에 이동할 칸이 1이면 안된다.3. 가로로 이동할 때(가로 또는 대각선) x 좌표만 +1이 된다.(x좌표는 N보다 작아야 함)4. 세로로 이동할 때(세로 또는 대각선)는 y 좌표만 -1이 된다.(y좌표는 0보다 커야 함)5. 가로 세로 대각선 모두 대각선으로 이동 가능하다.     하지만 대각선으로.. 2024. 7. 18.
1038번 - 감소하는 수 골드 5티어 감소하는 수라는 문제이다.예를들어 987, 210은 감소하는 수이지만, 100, 200은 감소하는 수가 아니다.N을 입력받고 N번째 감소하는 수를 구하는 문제이다. 문제를 보면 감소하는 수 중 가장 큰 수는 9,876,543,210이다.크기가 정해져있고, 몇번 써보다보면 감소하는 수는 많지 않다는 느낌이 올 것이다.즉, list에 감소하는 수를 모두 정리해주고, 그 list에서 해당 감소하는 수를 가져다가 쓰면 된다. list를 만드는 방법은 어떤 수를 맨 앞에 올 수로 정하고, 그 뒤에는 그 수보다 작은 수만 넣어주면 될 것이다.그리고 한번 정렬 해주고 N번째 요소를 빼주면 된다.그렇게 나온 식은 다음과 같다.import java.util.*;public class Main { sta.. 2024. 7. 18.
2667번 - 단지번호붙히기 단지번호붙히기라는 문제이다. 간단하게 설명하자면, 아래 그림과 같이 1이 모여있는 부분의 크기를 찾고 오름차순으로 정렬하라는 문제이다.생각보다 오래걸린 문제였다. 단순하게 주변을 둘러보며 찾는것을 꺼리고 뭔가 더 좋은 방법이 있지 않을까 너무 오랜시간 고민했기 때문이다. 혹시나 하는 마음에 풀이를 봤더니... 좀 실망스러웠다. 정말 단순하게 찾는 문제였기 때문이다.그렇게 방법을 알고 나서 문제를 풀었고, 아래와 같은 코드가 나왔다.import java.io.*;import java.util.*;public class 단지번호붙이기_2667번 { static int N; static int[][] map; static boolean[][] visited; static int[] dx .. 2024. 7. 18.

티스토리툴바