목록Algorithm-백준/BFS,DFS (9)
HS_development_log
1. 문제 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 접근 BFS문제다. 근데 구해야 하는 경우의 수가 2가지다. 적록색약일 때는 색구분을 2개로 하고, 적록색약이 아닐 때는 색구분을 3개로 해주면 된다. 적록색약 배열, 적록색약 아닐 때 배열 2가지를 만들어서 각각 처리해주면 된다. 3. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main{ public static ..
1. 문제 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net 가장 기본적인 BFS 문제입니다. 다만 상하좌우 뿐만 아니라 대각선으로도 이동이 가능한 점과 가로 세로의 입력값이 일반적인 경우와 달리 반대로 되어있는 점만 유의하면 어렵지 않았습니다. 2. 알고리즘 BFS 방식으로 모든 칸을 검사한다. 상하좌우 뿐만 아니라 대각선으로도 이동이 가능하므로 주의한다. 한번의 BFS 탐색이 끝날때 마다 섬의 개수를 +1 해준다. 3. 코드 /** * 2020.08.04 * DevHyeon * BOJ4963 : 섬의 개수 */ i..
1. 문제 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 2. 알고리즘 k개의 수 중에서 6개를 조합하는 문제이다. 경우의 수는 kC6. 재귀로 완전탐색을 실시하여 모든 조합을 찾은 후 출력한다. 재귀의 return조건은 6개를 조합해야하므로 detph==6. 3. 코드 /** * 2020.07.28 * 백준 6603 : 로또 * DevHyeonseong */ import java.util.*; public class BOJ6603 { public static int[] lotto; pub..
문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ... www.acmicpc.net BFS탐색 문제 한 번에 뻗어 나가는 범위가 8개다. 그 부분만 유의하면서 탐색하면 어렵지 않은 문제 알고리즘 시작할 때 현재..