알고리즘

[Java/자바 백준 1520] 내리막 길

풀이 DFS + DP 문제입니다 처음에 DFS로만 풀었는데 메모리 초과가 발생했습니다. 이를 보완하기 위해 DP 메모이제이션 방법을 추가했습니다. 나보다 더 낮은 경로일 때 탐색을 계속해서 진행했으며, 목적지까지 도착하면 dp +1 시켜주었습니다. DFS방식이기 때문에 dp가 -1 이 아닌 경우는 이미 끝까지 탐색한 경로이기 때문에 해당하는 dp를 바로 return 시켜주었습니다. import java.io.*; import java.util.*; // dfs + dp 문제 public class Main{ static int N, M; static int[][] map; static int[][] dp; static int[] dx = {-1,0,1,0}; static int[] dy = {0,-1,0..

[Java/자바 20055 백준] 컨베이어 벨트 위의 로봇

설명 문제 자체가 어렵진 않지만, 조건이나 설명이 헷갈린 문제였습니다. 컨베이어 벨트이고, N 이후에는 낭떠러지라고 생각하면 됩니다. 순환하는 원형이고 1~N까진 로봇이 존재할 수 있지만, N+1~2N까지는 존재 X 풀이 순서대로 진행하면 1. 과정에서 벨트와 로봇이 움직이게되는데, 이때 내리는 위치에 도달한 로봇은 즉시 내려갑니다. moveBelt() 2. 로봇이 앞에 칸에 내구도가 1이상이며, 로봇이 존재하지 않는다면 앞으로 이동하게 됩니다. 앞에 칸의 내구도는 -1. moveRobot() 3. 올리는 위치에 내구도가 1이상이면 로봇을 올려주고, 내구도를 -1 시켜줍니다. newRobot() 2,3번 과정에서 내구도가 -1되는 칸마다 0이 된 칸을 확인해주었습니다. import java.io.*; i..

[Java/자바 백준 19238] 스타트 택시

풀이 bfs를 이용하면서 collection sort 가 핵심인 문제 출발지와 도착지를 찾으면서 마지막에 남는 연료 값 출력하는 문제였으며, 승객 출발지 위치에 도달할 수 없거나, 승객을 태우고 도착지로 도달할 수 없는 경우 -1 출력, 또한 중간에 연료를 다 소진하게 되면 -1 출력해야합니다. 승객들을 찾는 과정에서 Taxi 클래스에서 time,row,col 순으로 collection sort를 해주고 조건에 맞는 승객을 태워 걸린 시간과 passengerMap에서 인덱스를 구해주고 Passenger 인덱스에 해당하는 도착지에 걸린시간을 도달하는 시간을 계산. package b0103; import java.io.*; import java.util.*; public class Main_bj_g4_192..

[Java/자바 백준 2589] 보물섬

풀이 bfs로 해결 가능한 문제 'L' 육지인 상황마다 가장 먼 육지와의 거리를 계산해주는 문제입니다. visited 를 -1로 모두 초기화해서 현재 위치와 가장 먼 육지를 계산하고 bfs가 진행될 때마다 현재 가장 먼 거리를 가지고 있는 answer와 비교 import java.io.*; import java.util.*; public class Main { static int N, M, answer; static char[][] map; static Queue queue = new LinkedList(); static int[] dx = {-1,0,1,0}; static int[] dy = {0,1,0,-1}; public static void main(String[] args) throws Exce..

[Java/자바 백준 14503] 로봇 청소기

풀이 문제 그대로 하나하나씩 진행하면 되는 문제였습니다. 현재 x,y 좌표와 바라보는 방향을 저장하고 왼쪽부터 청소할 수 있는지 비교해보며, 만약 청소할 수 없는 공간이 없다면 바라보는 방향 기준으로 후진을 진행했습니다. import java.io.*; import java.util.*; public class Main_bj_g5_14503_로봇청소기 { static int N, M, curX, curY, curDir, totalClean, dirCheck; static int[][] map; static boolean[][] visited; // 북 동 남 서 static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; public static ..

[Java/자바 백준 23288] 주사위굴리기2

풀이 삼성 가서 털렸던 문제.... 계속 풀고 싶어서 백준에 떠서 풀었는데, 디버깅도 한번도 안하고 바로 맞아버린 비운의 문제.. 코테때 로직 그대로 풀었는데.... 아무튼 풀이 시작하겠습니다 ! 저는 우선 방향을 동남서북으로 맞춰줘서 90도 시계일땐 +1 반시계 90도 일땐 -1 씩으로 dx, dy를 설정했습니다. 처음 동쪽 방향이니 dir=0 으로 설정 isAvailable에서 nx,ny값이 가능한지 보고, 범위 밖이면 dir을 변경해주었습니다. move 에서 nx,ny로 이동하고 dice_chage에서 주사위를 굴렸습니다. 주사위는 아래 동 서 남 북 위 으로해서 6 3 4 5 2 1 로 초기 설정하고 , 동서남북에 따라서 주사위가 값들이 어떻게 변경하는지 하나하나 바꿔주고, dir_change에서..

[Java/자바 백준 17143] 낚시왕

풀이 빡구현 문제 처음에 상어들을 2차원 리스트에 넣어줬습니다. 1~M까지 넣어주고 상어들을 넣어주고 map에는 상어들의 인덱스 값을 띄웠습니다 !! 서있는 y위치를 증가시키면서 첫째 find를 구현해서 땅과 가장 가까운 상어를 잡아 total에 더해주고, 해당 위치는 0으로 바꿔주었고 해당 인덱스 상어의 x값을 -1로 초기화 했습니다. 이유는 상어들을 이동시킬때 잡아먹힌 앤지 아닌지 판별하려고 했습니다. 둘째 상어들 이동단계에서 map을 우선 0으로 초기화 시키구 잡히지 않은 상어들을 이동시켰습니다. 조건에 따라 벽에 부딪힌다면, 반대쪽으로 가게 구현했습니다. map이 0이라면 해당 상어 인덱스를 map에 넣어주고 0이 아니라면 해당 위치에 있는 상어 크기와 현재 상어 크기의 값을 비교해주었습니다. i..

[Java/자바 백준 16235] 나무 재테크

풀이 문제 이해가 가장 중요한거 같습니다. 말이 좀 헷갈리게 해서 첫째줄은 N,M,K 이고 N은 맵의 크기, M은 나무 갯수, K는 몇년동안 진행하는지입니다. 그후 N개만큼 겨울에 양분이 추가되는 숫자가 나오구, 그다음 M개만큼 Tree에 x,y,age에 대한 정보가 나옵니다. 기본 map에는 전부 양분이 5인 디폴트 값이 있습니다. 나이가 낮은 나무들이 먼저 나올 수 있게 pq를 이용했습니다. 봄 ) 양분이 충분할 때와 충분하지 않은 경우로 나누어서 충분하다면 map[x][y]에 age만큼 감소하고, age를 +1씩 해주었습니다. 이때 tmp 큐에 넣어주었는데, 왜냐하면 tree가 pq로 만들어줬기 때문에 tree에 넣어준다면 나이가 어린 나무가 하나 들어가서 정렬이 바뀔 수도 있기 때문입니다. 충분하..

[Java/자바 백준 21610] 마법사 상어와 비바라기

풀이 단계별로 구현해주었습니다. 조건이 까다롭지도 않고 차근차근 읽어보면서 풀어보시는게 좋을거같아요. 1) 처음 구름에 위치는 고정되었으므로 cloud큐에 넣어주고 2) 구름을 옮겨주는 단계에서 오류가 발생하긴 했는데, 처음엔 s만큼 전부 도는 시간을 줄이려고 s/N을 해줬는데 대각선에서 틀리더라구요 그래서 s만큼 for문 돌렸습니다. 3) 대각선에 해당하는 1,3,5,7 에 해당하는 x,y를 탐색해주어서 0이 아니면 +1 씩 해주고 4) 다시 구름을 만들었을때 구름이 있던 장소를 담아두었던 check에서 false인 값과 && 2 이상인 것들만 담았습니다. import java.io.*; import java.util.*; public class Main { static int[] dx = {0,-1,..

[Java/자바 백준 16234] 인구이동

풀이 골드 5인데 비교적 더 쉬운거 같습니다. 조건도 쉬운 편이구 BFS를 이용를 이용해서 check가 false 일 경우 탐색을 시작해서 조건 사이에 있다면 queue에 넣어주는 방식으로 탐색을 진행했습니다. tmp에 큐를 임시로 저장해서 해당하는 값들의 x,y 값들을 전부 집어넣어주고 cnt가 1이 아니라면 그 값들을 모두 꺼내어 인구 이동의 평균값을 구해줬습니다. import java.io.*; import java.util.*; public class Main { static int N,R,C, union ,res,cur_x,cur_y; static int[][] map; static int[] dx = {1,-1,0,0}; static int[] dy = {0,0,1,-1}; static boo..