밤이 블로그

BOJ#12851 숨바꼭질 2 * 문제https://www.acmicpc.net/problem/12851 * 풀이 쉬운 문제인데 푸는데 고생을 좀 했습니다. 일단은 1697 숨바꼭질 문제와 동일한데..동생을 찾는 가장 빠른 시간을 출력하는 것과가장 빠른 시간으로 찾는 방법의 개수까지 출력해야 합니다. 헷갈리지 말아야 할 것은 가장 빠른 시간으로 찾는 '경로'가 아니라 '방법'의 개수 입니다. 즉, 입력 데이터가 1 10일 때가장 빠른 경로는 1 -> 2 -> 4 -> 5 -> 10 이지만방법으로 따지면 아래와 같이 2가지가 있습니다.1 -> 2(+1) -> 4(*2) -> 5(+1) -> 10(*2)1 -> 2(*2) -> 4(*2) -> 5(+1) -> 10(*2) 따라서 방법의 개수를 구하려면 큐에 ..

BOJ#1062 가르침 * 문제https://www.acmicpc.net/problem/1062 * 풀이 꽤 어렵게 푼 문제입니다. 이 문제는 주어진 단어들을 어떤 자료구조에 담는지가 핵심인 것 같습니다. 1. 단어를 읽을 수 있다는 것은 그 단어를 이루고 있는 알파벳을 모두 알고 있다는 것입니다. -> 따라서 단어를 입력 받을 때, 불필요한 정보는 받지 말고 각 단어를 이루고 있는 알파벳의 모음으로 입력을 받습니다.-> 즉 antahellotica 단어는 [a, n, t, h, e, l, o, i, c] 으로 입력을 받으면 됩니다.-> 처음에는 중복되는 알파벳은 받지 않고 순서는 상관 없으므로 HashSet을 이용하려 했지만 재귀 형태에서 iteration을 사용하는 것에 불편함이 있어서 , 조금 더 ..

BOJ#1707 이분 그래프 * 문제https://www.acmicpc.net/problem/1707 * 풀이 그래프 관련 기본 문제입니다. 저는 BFS/DFS로 풀었는데, 주의할 점으로 연결 그래프와 비연결 그래프를 둘 다 고려해주어야 합니다, * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231707_BipartiteGraph/src/Main.java (BFS)import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /** * BOJ#1707 이분 그래프 * https://www.acmicpc.net/p..

BOJ#13422 도둑 * 문제https://www.acmicpc.net/problem/13422 * 풀이 푸는건 어렵지 않지만 시간 제한에 신경을 써서 구현해야 합니다. → O(nm)으로 구현 시 시간초과, 따라서 O(n)으로 해결을 해야 합니다. 시간 초과, 코드 길이, 푸는 속도 등에 초점을 맞춰 풀어보시면 좋을 것 같습니다. 풀이의 요점은 이전 Iteration에서 사용했던 sum에서 필요없는 값은 빼고, 더할 값만 더해서불필요한 연산을 하지 않는 것입니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%2313422_Theif

BOJ#2178 미로 탐색 * 문제https://www.acmicpc.net/problem/2178 * 풀이 bfs(Breadth First Search) 기본 문제입니다. 개념만 알면 풀 수 있는 문제이기 때문에설명은 생략하겠습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232178_MazeSearching/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringToke..

BOJ#11403 경로찾기* 문제https://www.acmicpc.net/problem/11403 * 풀이 가중치 없는 방향 그래프가 행렬로 주어졌을 때, i에서 j로 가는 경로 유무를 행렬로 표현하라. bfs(Breadth First Search)를 이용하였다. 1. bfs(i, j) : i를 시작점으로 해서 연결된 모든 노드를 탐색한다. j를 찾을 경우 return.2. 위 과정에서 탐색한 노드는 중복해서 탐색하지 않도록 한다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2311403_BFS_FindPath/src/Main.java Java (17.08.29)import java.io.*; import java.util.LinkedList;..