BFS33 [프로그래머스] Lv.2 타겟 넘버 JAVA 풀이 문제 Lv.2 타겟 넘버 (dfs, bfs)n개의 음이 아닌 정수정수들을 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만들자예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있다-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3 [과정] 탐색하자 → 브루트포스 / dfs 1. count 계산은 맨 마지막에모든 넘버들을 다사용해서 타겟넘버를 만들어야해서 마지막까지 가고나서 타겟넘버랑 같으면 count++각자 타고 타고 들어가 dfs를 실행하면 count 별도 연산 없이도 차곡차곡 쌓인다!-> 최종적으로 solution메서드에서 그렇게 쌓인 count만 출력해주면 끝 2. for문을 .. 2025. 3. 18. [백준] 2573번 빙산 JAVA (자바) 풀이 문제 2573번 (BFS) : 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장 바다 = 0 2453 3 252 7624 : 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 준다 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다 (0보다 더 줄어들지 않는다) 241 1 15 5412 1년 후 빙산 : 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력 [입력] : 첫 줄에는 행의 개수와 열의.. 2024. 8. 6. [백준] 2636번 치즈 JAVA (자바) 풀이 문제 2636(BFS) : 회색으로 표시된 부분 = 치즈 X친 부분 = 판의 가장자리 (치즈 없음) ‘c’로 표시된 부분만 한 시간 후에 녹고 빈칸과 접촉하는 치즈는 c 표시 해준다 단 치즈로 둘러쌓여있는 빈칸은 접촉해도 c표시 없어도 된다 : 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각 개수 구해라 [입력] : 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수 (길이는 최대 100) 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 (치즈가 없는 칸은 0, 치즈가 있는 칸은 1) [출력] : 첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력 : 둘째 줄에는 모두 녹기 한 시간.. 2024. 7. 13. [백준] 3055번 탈출 JAVA (자바) 풀이 문제 3055(BFS) : 티떱숲의 지도는 R행 C열로 이루어져 있다 비어있는 곳은 . 물이 차있는 지역은 * 돌은 X 비버의 굴은 D 고슴도치의 위치 S : 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동가능 물도 매 분마다 인접한 비어있는 칸으로 확장 물과 고슴도치는 돌을 통과할 수 없다 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다 : 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램 (다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다) [입력] : 첫째 줄에 50보다 작거나 같은 자연수 R과 C : 다음 R개 줄에는 티떱숲의 지도 .. 2024. 7. 12. [백준] 9019번 DSLR JAVA (자바) 풀이 문제 9019(BFS) : 네 개의 명령어 D, S, L, R 계산기에는 레지스터 = 0 이상 10,000 미만의 십진수 저장 가능 예) 레지스터에 저장된 n (n의 네 자릿수를 d1, d2, d3, d4) 즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)D = n x 2 (결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지)S = n - 1 (n이 0 이라면 9999 가 대신 레지스터에 저장)L = n의 각 자릿수를 왼편으로 회전 (d2, d3, d4, d1)R = n의 각 자릿수를 오른편으로 회전 (d4, d1, d2, d3) : A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램 [입력] : 첫 줄에 T 개의.. 2024. 7. 11. [백준] 16234번 인구 이동 JAVA (자바) 풀이 문제 16234(BFS) : N×N크기의 땅 각 땅에는 나라가 하나씩 존재 ( r행 c열에 있는 나라에는 A[r][c]명이 산다) : 인구 이동이 없을 때까지 지속된다.붙어있는 두 나라의 인구 차이가 L명 이상, R명 이하라면 인구 이동 시작인접한 칸만을 이용해 이동할 수 있으면 연합연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)편의상 소수점은 버린다연합을 해체하고 모든 국경선을 닫기 : 각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램 [입력] : 첫째 줄에 N, L, R (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100) 둘째 줄부터 N개의 줄에 각 나라의 인구수 r행 c열에 주어지는 정수는 .. 2024. 7. 11. [백준] 9205번 맥주 마시면서 걸어가기 JAVA (자바) 풀이 문제 9205(BFS) : 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발 맥주 한 박스에는 맥주가 20개 맥주 1병에 50미터 전진 가능 편의점에 들렸을 때, 빈 병은 버리고 새 맥주를 살 때 박스에 들어가는 총 맥주가 20병을 넘을 수 없다 (편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다) 편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다 [입력] : 첫째 줄에 테스트 케이스의 개수 t (t ≤ 50) 테스트 케이스의 첫째 줄에는 편의점의 개수 n (0 ≤ n ≤ 100) 다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 미터 좌표 ( -32768 ≤ x, y ≤ 32767) 두 좌표 사.. 2024. 7. 6. [백준] 16928번 뱀과 사다리 게임 JAVA (자바) 풀이 문제 16928(BFS) : 주사위를 조작해 원하는 수를 만들면 최소 몇 번만에 도착할까 게임은 크기가 10×10이고, 총 100개의 칸으로 된 보드판은 1~100까지 수가 적혀있다 주사위를 굴려 나온 수만큼 이동 : 예) 현위치 = i / 주사위 = 4라면 i+4번 칸으로 이동 : 도착칸 = 사다리 경우 위로 이동 / 도착칸 = 뱀 경우 뱀을 따라 이동 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있다 (동시에 둘 다 갖는 경우는 없다) : 게임의 목표 = 1번 칸에서 시작해서 100번 칸에 도착하는 것 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값 구하기 [입력] : 첫째 줄에 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(.. 2024. 7. 3. [백준] 13549번 숨바꼭질 3 JAVA (자바) 풀이 문제 13549(BFS) : 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다 현 위치가 X일 때 걷기 = 1초 후에 X-1 또는 X+1로 이동 순간이동 = 0초 후에 2*X의 위치로 이동 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구해라 [입력] : 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K [출력] : 동생을 찾는 가장 빠른 시간을 출력 [문제접근] 1. 기존 숨바꼭질 1697번과 차이점!기존 문제에서는 모든 이동이 동일한 1초를 소요현 문제에서는 순간 이동은 0초 / 걷기 이동만 1초 소요 2. 출력 배열 사용하지 말고 큐에다 넣어버리기count[] 배열보다 .. 2024. 7. 3. [백준] 2589번 보물 JAVA (자바) 풀이 문제 2589(BFS) : 보물섬 지도의 각 칸은 육지(L)나 바다(W)로 표시 이동은 상하좌우로 이웃한 육지로만 가능, 한 칸 이동하는데 한 시간이 걸린다 보물은 육지 두 곳에 나뉘어 묻혀있고 두 곳을 이동하는 최단거리를 구해라 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다 예) 보물은 아래 표시된 두 곳에 묻혀 있고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간 [입력] : 첫째 줄에는 지도의 가로, 로 ( 가로, 세로의 크기는 각각 50이하 ) : 다음 줄부터 L과 W로 표시된 보물 지도 (빈칸없이) [출력] : 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력 [문제접근] 1. 출력 배열 사용하지 말고 큐에다 넣어버리기co.. 2024. 6. 21. 이전 1 2 3 4 다음
