BFS11

• 

  [백준][Java] 2585 - 경비행기 문제 정보https://www.acmicpc.net/problem/2585 난이도 : G2유형 : 이분탐색, BFS문제 풀이S에 T로 갈 때 연료 급료 횟수가 K이하가 되도록 최적의 연료통의 크기를 구하면 된다. 연료통의 크기에 따라 'K 이하로 도착할 수 있다' VS 'K 이하로 도착할 수 없다'즉, 두 가지 경우가 발생하며 연료통의 크기에 따라 결과는 N, N , N,.... Y, Y Y 이런 형태가 나온다.위의 형태에 따라 연료통의 크기는 이분탐색을 통해 찾아낼 수 있다. 이분탐색으로 얻은 연로통의 크기를 기준으로시작점부터 시작하여 도착점까지 경유지를 포함하여 BFS 탐색을 진행하면 된다.BFS 결과를 통해 매번 이분탐색으로 연로통의 크기를 조절하며 최적의 값을 찾을 때까지 BFS을 진행하면 된다... Algorithm, Problem Solving/백준(boj) 2025. 3. 11.

• 

  [백준][Java] 2288 - 격자의 분리자 1. 문제 정보https://www.acmicpc.net/problem/2288난이도 : G5유형 : BFS, DFS, DP시간 : O(S)2. 문제 풀이최단 경로를 찾기 위해 위아래로 연결되어 있는 S 집합의 좌우 폭을 넓혀야 한다.넓히는 이유는 S로 이루어진 길에서 탐색의 경로의 경우의 수를 늘려 최소 거리를 찾기 위함이다. 문제 조건을 보면 B는 S로 변경할 수 있다, 단 왼쪽에 S가 있는 B만 변경할 수 있다.즉 S와 B가 붙어 있는 경우에만 B를 S로 변경할 수 있다 입력된 문자열을 통해 테이블을 초기화할 때각 줄마다 처음 등장하는 B를  S로 바꾼다 결과적으로 기존의 테이블에서 변경된 테이블의  S의 모양은 오른쪽으로 1칸씩 확장된 모양이다.(단, 문제의 제약사항에 따라 테이블의 꼭짓점에는 S.. Algorithm, Problem Solving/백준(boj) 2024. 5. 1.

• 

  [백준][Java] 6129 - Obstacle Course 목차 문제 정보 https://www.acmicpc.net/problem/6129 6129번: Obstacle Course The cow must make at least 2 turns: For example, the cow may start by facing south, move south, turn to face west, move west, move west, then turn to face south, and finally move south into the B square. www.acmicpc.net 난이도 : G4 유형 : 다익스트라, BFS 문제 풀이 우선순위 큐를 이용한 다익스트라 기법을 활용하여 풀었다. (0-1 BFS라고도 봐도 무방하다) 우선순위 큐에 들어 있는 데이터는 '회전 횟수.. Algorithm, Problem Solving/백준(boj) 2023. 12. 11.

• 

  [백준][Java] 23288 - 주사위 굴리기 2 목차 문제 정보 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 난이도 : G3 유형 : 시뮬레이션, BFS, 해쉬 문제 풀이 [핵심] 1. 매번 주사위가 움직일 때마다 주사위의 6면 상태를 관리 2. 매번 이동 방향의 인덱스(dirIdx)를 알맞게 조정 [최적화] 매번 점수를 구할 때 항상 탐색을 하면 비효율적이다. 해쉬맵을 이용하여 BFS 탐색 종료 후 탐색되었던 곳들을 하나의 그룹번호로 묶고 해당 그룹의 총점수를 해쉬맵에.. Algorithm, Problem Solving/백준(boj) 2023. 10. 12.

• 

  [백준][Java] 15240 - Paint bucket 목차 문제 정보 https://www.acmicpc.net/problem/15240 15240번: Paint bucket One of the most time-saving operations when drawing on a computer (for example using Photoshop) is the “bucket fill” operation. When you select this tool and click on a (target) pixel of the image it will fill all the pixels that have the same color www.acmicpc.net 난이도 : S1 유형 : BFS, DFS 문제 풀이 상하좌우로 같은 문자를 탐색하면서 치환해 주면 된다. 여기서 주.. Algorithm, Problem Solving/백준(boj) 2023. 10. 10.

• 

  [백준][Java] 14397 - 해변 목차 문제 정보 https://www.acmicpc.net/problem/14397 14397번: 해변 단위 정육각형 이루어져 있는 지도가 주어졌을 때, 해변의 길이를 구하는 프로그램을 작성하시오. 해변은 정육각형의 변 중에서 한 쪽은 물인데, 한 쪽은 땅인 곳을 의미한다. www.acmicpc.net 난이도 : Silver 4 유형 : BFS, 그래프 탐색 문제 풀이 사각형을 다루는 일반적인 인접행렬과 달리 이 문제는 '육각형'이다. 그러므로 이동하는 방향이 6가지이며 또한 홀수, 짝수 줄마다 이동하는 방향이 다르다. ( 육각형들이 붙어 있지 않고 상하좌우로 정렬되어 있다고 생각해 보자) 홀수줄 : (-1,-1), (-1,0), (0,1), 그림처럼 짝수, 홀수줄마다 이동하는 방향이 다르다는 것을 알 .. Algorithm, Problem Solving/백준(boj) 2023. 4. 22.

• 

  [백준][Java] 7562 - 나이트의 이동 목차 문제 정보 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 난이도 : Silver 1 유형 : BFS 문제 풀이 인접한 상하좌우로 움직이던 스탠다드한 BFS문제에서 상하좌우가 아닌 체스의 나이트말의 처럼 이동방법을 변경한 간단한 문제이다. bfs의 정석풀이에서 이동방향만 바뀐 풀이여서 풀이는 생략하겠다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io... Algorithm, Problem Solving/백준(boj) 2023. 4. 3.

• 

  [백준][Java] 6186 - Best Grass 목차 문제 정보 https://www.acmicpc.net/problem/6186 6186번: Best Grass Bessie is planning her day of munching tender spring grass and is gazing out upon the pasture which Farmer John has so lovingly partitioned into a grid with R (1 Algorithm, Problem Solving/백준(boj) 2023. 3. 31.

• [백준][Java] 6593 - 상범 빌딩 목차 [프로그래머스][Kotlin] - [codeforces][Kotlin] - 문제 정보 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 난이도 : G5 유형 : BFS 문제 풀이 상 하 동 서 남 북 6가지 방향으로 이동할 수 있는 3차원 BFS 문제 스탠다드한 BFS풀이에서 z축으로 확장만 시켜주면 쉽게 풀 수 있는 문제이다. 아래 코드를 최적화한다면 출구를 만났을 때 다시 큐에 넣지 말고 바로 탐색을 종료하면 된다. 코드 import jav.. Algorithm, Problem Solving/백준(boj) 2023. 3. 27.

• [백준][Java] 9205 - 맥주 마시면서 걸어가기 목차 문제 정보 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 난이도 : G5 유형 : 그래프 탐색, BFS 문제 풀이 필자는 BFS로 해결했다. 이 문제에서 20개의 병의 개수 조건이 있지만 신경 쓸 필요가 없다. 왜냐하면 상근이는 도착지 외엔 편의점만 경유하기 때문이고 편의점에 들르기만 하면 다시 병 20개를 채울 수 있기 때문에 병의 갯수와 상관없이 현재 위치에서 다음위치까지의 맨해튼 거리가 1000 이하이면 항상 이동할 수 있다... Algorithm, Problem Solving/백준(boj) 2023. 3. 25.

• [백준][Java] 17070 - 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도 : G5 유형 : DP, DFS, BFS 문제 풀이 처음에 BFS로 풀었다가 시간초과가 떠서 DP로 방향을 바꿨다. dp[N][N][3] ) dp[N][N][0] = 가로 dp[N][N][1] = 세로 dp[N][N][2] = 대각선 dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2] => 현재 가로 = 이전 가로 + 이전 대각선 dp[i.. Algorithm, Problem Solving/백준(boj) 2023. 3. 24.