https://www.acmicpc.net/problem/12919 S에서 T로 진행되도록 하면 종단점을 설정하는 것이 어려워T에서 S로 가도록 했다. BFS 문제 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;//A//BA q = new LinkedList(); q.add(T); while(!q.isEmpty()){ String str = q.poll(); if(S.length() > str.length()){ ..

https://www.acmicpc.net/problem/4179 불이 여러개가 존재한다는 것을 잘 생각해야 하는 문제. BFS 사용 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br..

Union-Find 알고리즘 유니온 파인드 알고리즘을 사용하는 문제이다.오랜만에 유니온 파인드를 사용한 것 같다. 이 문제는 연결을 끊거나 연결을 생성함으로 하나의 트리를 형성하는 것이다. 따라서, 입력받을 때 사이클이 존재한다면 해당 연결을 끊어야 하므로, 값을 증가시켜주고만약, 연결이 끊어져있는 곳이 있다면 이어줘야 하므로 union으로 합처준 뒤 값을 증가시킨다. 이때, 나는 1(최소값)으로 유니온 파인드가 진행되게 했으므로, 1이 아닌 경우 이어주게 해줬다.  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public clas..

https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  주석에 설명해 놓긴 했지만, 뭔가 그래프 문제보다 DP에 가까운 느낌이라고 해야되나플로이드 워샬 같기도 하면서 살짝 다른거 같다. 로직 자체는 모든 정점을 방문하면서 확인한다는 부분은 비슷하지만, 결국 최단거리를 구하지도 않을 뿐더러반복문 순서도 플로이드-워샬과 살짝 다르다. 플로이드 워샬은 k를 돌면서 점차 가장 짧은 걸 구해가지만, 이 문제는 그냥 i번째에는 i번째에 끝나서 뭔가 좀 다른 느낌이..

문제를 올바르게 이해하는 것이 중요하다. 시간복잡도BFS를 Q번 반복하는 문제이다. 인접리스트 BFS의 시간복잡도는 통상적으로 O(V+E)">O(V+E)이므로, 시간복잡도는 O(Q×(V+E))">O(Q×(V+E))가 된다. V와 E는 각각 최대 5000이고, Q는 최대 5000이다.(5000+5000)×5000=104×5×103=5×107<108">(5000+5000)×5000 10^8 == 100000000(1억)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class BOJ1..

import java.util.*;class Solution { public int solution(int[][] data, int col, int row_begin, int row_end) { int answer = 0; Arrays.sort(data, (o1, o2) -> { if(o1[col - 1] == o2[col- 1]){ return o2[0] - o1[0]; } return o1[col - 1] - o2[col - 1]; }); List modSum = new ArrayList(); for(int..