밤이 블로그

BOJ#1613 역사 * 문제https://www.acmicpc.net/problem/1613 * 풀이플로이드 와셜 알고리즘에 따라 Start -> 임의의 노드 -> End를 만족하는 임의의 노드가 존재할 때 (자기 자신을 포함하여) Start -> End 를 만족함을 알 수 있습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/644019c1ecb2b486c6597f4c2570edae8f97760f/BOJ%231613/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer..

BOJ#2593 엘리베이터 * 문제https://www.acmicpc.net/problem/2593 * 풀이다익스트라를 이용해서 풀었습니다. 처음에 그래프 모델링에서 당황했는데 아래와 같이 해보았습니다.문제에 나와있는 예제에서 ArrayList elevator = new ArrayList();elevator : 각 엘리베이터에서 갈 수 있는 층 엘리베이터 1번 : [4, 7, 10]엘리베이터 2번 : [7, 12]엘리베이터 3번 : [4, 8, 12] ArrayList floor = new ArrayList();floor : 각 층에서 탈 수 있는 엘리베이터 4층 : [1, 3]7층 : [1, 2]8층 : [ 3 ]10층 : [ 1 ]12층 : [2, 3] 그리고 정점을 각 층이 아닌 엘리베이터로 정하였..

BOJ#4191 Dominos 2 * 문제https://www.acmicpc.net/problem/4191 * 풀이어렵지 않은 문제였습니다.풀이는 아래 코드로 대체합니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%234191/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static ArrayList edge; static boolean[] visited;..

BOJ#2412 암벽 등반 * 문제https://www.acmicpc.net/problem/2412 * 풀이BFS를 통해 암벽 정상까지 최소 이동 횟수를 구하면 됩니다.- 일단 Start 노드를 시작으로 인접한 노드들을 탐색하고 조건에 맞는 노드들만 다시 Queue에 넣어줍니다.- 조건 : |a-x| o2.col) return 1; if (o1.col == o2.col) { if (o1.row o2.row) return 1; } return 0; }; Queue queue = new LinkedList(); queue.add(new Node(0, 0)); int step = -1; while (!queue.isEmpty()) { step++; ..

BOJ#1963 소수 경로 * 문제https://www.acmicpc.net/problem/1963 * 풀이- 구하는 것 :두 소수 변환에 필요한 최소 변환 횟수 (최단 경로, 가중치 1이고 경우의 수가 많지 않으므로 BFS 탐색 가능) - 조건 : 4자리수, 소수로만 이동 가능, 중복 방문 x - 예를 들어 Test Case가 '1033 8179'인 경우 step = 0;1) 1033에서 한자리수를 변경해서 만들 수 있는 모든 소수들을 구한 후 Queue에 넣는다. (step = 1)2) step == 1인 Queue에 들어있는 모든 수에 대해 반복 (step = 2)3) step == 2인 Queue에 들어있는 모든 수에 대해 반복 (step = 3)....결국 step == n에서 8179를 찾게 ..

BOJ#1890 점프 * 문제https://www.acmicpc.net/problem/1890 * 풀이dp + dfs로 풀었습니다.정답 비율에 비해 문제가 굉장히 쉽습니다. N 범위와 경로의 개수 범위(long)만 주의하면 될 것 같습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231890/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static final int[] dRow = {0, 1}; stat..

BOJ#10216 Count Circle Groups * 문제https://www.acmicpc.net/problem/10216 * 풀이주어진 노드들은 결국 disjoint sets를 형성합니다. 따라서 Union-Find 자료구조를 이용해보았습니다. Two sets are said to be disjoint if they have no element in common. (출처 : https://en.wikipedia.org/wiki/Disjoint_sets) 해야 할 일은 3가지입니다. 1. 노드 간 거리 비교 : 거리 비교 시 양변을 제곱하여 비교하였습니다. 2. 비교 결과에 따라 노드를 그룹으로 묶기 : Union-Find 자료구조 사용 3. 그룹 개수 출력하기 : UnionFind Class에 c..

BOJ#10429 QUENTO * 문제https://www.acmicpc.net/problem/10429 * 풀이 dfs 탐색으로 풀었습니다. 개인적으로 문제가 너무 재미있었습니다. 어렵지 않아서 풀이는 생략. * 나의 코드https://github.com/stack07142/BOJ/blob/646def24b7052ba5f4f933c5bfbc7fa9c1b65ce3/BOJ%2310429_QUENTO/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * 선데이코딩 베타라운드1 - D. 수학 퍼즐 게임 * BOJ#10429 QUENTO * https://www.acmicpc.net/problem/10429 */ public class ..

BOJ#1525 퍼즐 * 문제https://www.acmicpc.net/problem/1525 * 풀이종만북을 참고하여 풀었습니다.To-Do : bfs, 양방향탐색, dfs 방법으로 각각 풀어보기 저는 이번에 bfs와 비트마스크를 이용해보았습니다. 맵은 하나의 정점으로 볼 수 있습니다. (총 정점의 수는 9! : 1부터 9까지 순서대로 나열하는 경우의 수와 같다) 그리고 상하좌우 4방향으로 이동할 수 있으니, 한 정점에서 최대 4개의 정점과 연결될 수 있습니다.즉, 주어진 정점에서 시작하여 4방향 탐색을 해나가면서 목표를 찾으면 되겠습니다. 문제는 어떻게 중복 방문을 체크하고 처리할 것인지 생각해봐야 합니다.저는 비트마스크를 이용해보았습니다. 각 값은 0부터 8사이의 값이므로, 각 값은 4비트를 사용하면..

BOJ#14502 연구소 * 문제https://www.acmicpc.net/problem/14502 * 풀이2017년 상반기 삼성 SW 역량평가 기출문제 입니다. 벽을 항상 3개 설치해서 안전영역의 최대값을 구해야 하는 문제입니다.즉, 완전 탐색이 필요합니다. (모든 경우를 다 해봐야 최대값을 구할 수 있음) 저는 아래와 같이 풀어보았습니다. 1. 조합을 돌려서 Map에서 빈칸 3개를 선택한 후 벽으로 바꿔줍니다. 최대 8*8 맵에서 빈칸 3개를 선택할 때 경우의 수 = (64-2)C3(바이러스가 최소 2개 있으므로) 2. 해당 Map에서 바이러스를 퍼뜨립니다. 3. (맵의 크기 - 바이러스의 수 - 벽의 수) 의 최대값을 갱신합니다. 4. 1~3 반복 * 나의 코드 https://github.com/s..