알고리즘

[Java/자바 백준 14226] 이모티콘

풀이 문제에 대한 이해가 어려운 문제였다. 문제 조건은 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. - > 클립보드 = 화면 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. - > 화면 += 클립보드 화면에 있는 이모티콘 중 하나를 삭제한다. -> 화면 -= 1 각각의 연산이 1초씩 걸립니다. (저는 문제를 잘못 이해했었는데 1, 2, 3단계로 모든 단계를 마치면 1초가 걸린다라고 이해를 했어요 ㅜㅜ) 처음 조건이 화면에 한개가 있고, 1번 연산, 2번 연산, 3번 연산을 각각 써줘서 가장 최소의 시간으로 S까지 도달하는 초를 구해주면 됩니다. 2차원 boolean 배열을 따져줘서 이미 방문한 곳은 방문하지 않게 만들구, 각각의 조건에 맞게 구현해주었습니다. import java.i..

[Java/자바 SWEA 1953] 탈주범 검거

풀이 import java.io.*; import java.util.*; // 뱡항을 중심으로 1번은 4방 돌리고 // 2~7 은 들어온 방향으로 돌려야할거같은데 // 상 우 하 좌 public class Solution { static int n,m,r,c,l, time; static int[][] map; static boolean[][] check; static Queue queue= new LinkedList(); static int[] dx= {-1,0,1,0}; static int[] dy= {0,1,0,-1}; //hole에 위치를 기준으로 들어온 방향이 갈 수 있는 곳으로 설정하자. // 들어오는 방향마다 가능한거 -1 // 상: 1,2,5,6 // 우: 1,3,6,7 // 하: 1,2,4..

[Java/자바 백준 1504] 특정한 최단 경로

풀이 다익스트라를 이용하는 문제 v1, v2를 꼭 찍어서 N에 도달해야하므로 0 -> v1 -> v2 -> N 0 -> v2 -> v1 -> N 두가지 케이스를 나눠서 다익스트라 진행하면 됩니다. 92%에서 계속 틀리신분들 2 0 1 2 이 반례 처리를 안해서 그런거 같습니다 ! import java.util.*; import java.io.*; public class Main { static int V, E; static final long INF = Long.MAX_VALUE; static List[] adjList; static long[] distance; static boolean[] visited; public static void main(String[] args) throws Excepti..

[Java/자바 백준 1459] 걷기

풀이 그리디 문제인지만 모든 케이스를 다 고려해주었습니다. 헷갈릴 수 있는 상황 -> (0,0) (2,0) 가기 1. 직진해서 2W로 갈 수 있지만, 2. 0,0 -> 1,1 -> 2,0 이렇게도 갈 수 있습니다 지도가 무한히 크므로 다음 케이스별로 모든 조건을 비교해주어서 가장 작은 값을 출력시켰습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long X, Y, W, S; StringTokenizer st =..

[Java/자바 백준 1781] 컵라면

풀이 문제들을 deadLine이 작은 순, 받을 수 있는 컵라면 갯수가 큰 순으로 arraylist에 정렬했습니다. 컵라면을 최대한 많이 받으려면 deadline순으로 라면이 가장 많이 얻을 수 있도록 그리디하게 탐색해야하기 때문입니다. PriorityQueue를 사용해서 queue를 minHeap이라고 생각해줍시다. arr에 정렬되있는 값들을 탐색하면서 1. 큐 사이즈가 현재 데드라인보다 작다면 - 큐에 삽입을 해줍니다 2. 만약 큐 사이즈와 현재 데드라인이 같다면 큐의 peek(현재까지 얻을 수 있는 라면 중 가장 최솟값)과 비교를 해줍시다. 만약 peek가 작다면 빼주고 현재 라면수를 넣어주도록 합시다. 마지막으로 큐에 들어간 값들을 모두 더해주면 됩니다 ! import java.io.*; impo..

[Java/자바 백준 23290] 마법사 상어와 복제

풀이 문제를 읽다보면 주어진 조건이 너무 많다는 걸 알 수 있다.. 우선 map 자체를 뭐로 선언해야할까 효율적일까 고민하다가 list로 선언하기에 삭제나 삽입할때 문제가 생길거 같아서 2차원 큐 형태로 물고기의 방향 값을 갖도록 설계했습니다. 1. copyFishmap() : 맵에 있는 물고기들 전부 복사하기 map에 사이즈만큼 값을 copy[][]에 넣어줬습니다. 2. moveFish() : 물고기 이동 해당 맵 인덱스에 물고기가 있다면, 자신이 바라보는 방향부터 시작해서 반시계 45도로 탐색을 시작했습니다. 상어, 물고기 냄새, 격자 밖은 못가주게 해주었고 만약 8방향 탐색 후 모두 갈 수 없다면 제자리에 있도록 해주었습니다. 3. moveShark() : 상어 이동 순열을 이용했습니다. 저는 순열..

[Java/자바 백준 16928] 뱀과 사다리 게임

풀이 우선 최솟값을 위해 BFS를 사용했습니다. 1차원 배열을 길이가 100으로 선언하고 0으로 초기화 해줍니다. 해당 인덱스에 사다리나 뱀이 있다면 이동하게되는 위치를 넣어주고 0에서부터 큐에 삽입하여 게임을 시작합시다 ! 1~6에 주사위에 따라 전진하면서 해당값을 방문했는지, 범위에 벗어나지 않는지, 배열에 사다리, 뱀이 있는지 판단해주며 100에 도달시 (배열이라 인덱스는 99입니다) 걸린 시간을 출력해주면 되는 문제 입니다 ! import java.io.*; import java.util.*; public class Main{ static int[] map; public static void main(String[] args) throws Exception{ BufferedReader br = n..

[Java/자바 백준 16954] 움직이는 미로 탈출

풀이 8X8 맵에서 캐릭터는 인접한 곳 8방향 탐색과 제자리에 위치할 수 있습니다. 턴마다 캐릭터가 먼저 이동하고 난 뒤, 벽들이 아래로 떨어집니다. 저는 dfs로 진행하면서 1. 8방향 탐색으로 빈칸(.)의 위치를 찾고 2. 빈칸 위치 바로 위가 벽(#)이라면 continue 3. dfs로 진행하므로 다른 방향 탐색할 때 영향을 주면 안되므로 값을 copy했습니다. copy 과정에서 시간을 줄이기 위해서 flag를 사용해서 true면 리턴시켰고 벽이 아래로 떨어지게 되면 빈칸이 맨 윗줄에 생기므로 캐릭터가 row = 0 에 도달하게되면 flag = true 로 처리했습니다. import java.io.*; import java.util.*; public class Main { static char[][..

[Java/자바 백준 1976] 여행가자

풀이 유니온 파인드 문제 문제 핵심은 연결되었는지에 대해 물어보는 문제 매개체 도시가 있어서 1 - 3 도시가 서로 연결 되어있지 않아도 1 - 2 - 3 이 연결 되었으면 연결된 것 ! parents 배열을 만들어주고 먼저 자기 자신을 부모로 갖게 설정한 뒤, 입력을 받으면서 1인 경우(연결된 경우)에 한해서 유니온 파인드를 적용해주었습니다. 연결된 경우 이므로 a, b 둘중 인덱스가 큰 숫자를 작은 인덱스에 자식으로 갖게 만들어주었습니다. ex) union (0, 4) 일경우 이 상태에서 union (2,4)가 들어온다면 aRoot = 2 이지만 bRoot는 4 -> 0 이므로 bRoot = 0이 됩니다. 그렇다면 parents 배열은 이런식으로 바뀌겠죠 ! 유니온 파인드를 모두 적용 시킨 후, 정해..

[Java/자바 백준 17406] 배열돌리기 4

풀이 연산 수행 순서에 따라 최솟값이 변하므로 순열을 사용했습니다. 순열 뒤, 배열을 돌려줘야하는 배열 돌리기 구현 부분이 조금 헷갈린 문제 배열 돌리는 함수는 재귀로 구현했으며, 시작 x, 시작 y, 끝 x, 끝y 를 구해주고 시작 + 1과 끝 - 1 함수를 돌리면서 둘 값이 같아지면 min값을 구하는 식으로 구현했습니다. 또한 배열을 돌릴때, 네 부분으로 나누어서 구현했습니다. (시작 x, 시작 y) ~ (시작 x, 끝y) 오른쪽으로 배열 당기기 (시작 x, 끝 y) ~ (끝 x, 끝y) 아래쪽으로 배열 당기기 (끝 x, 끝 y) ~ (끝 x, 시작y) 왼쪽으로 배열 당기기 (끝 x, 시작 y) ~ (시작 x, 시작y) 위쪽으로 배열 당기기 이런 식으로 구현하고 각자 모서리 부분은 따로 저장해주었는데..