본문 바로가기

Baekjoon/[5] DFS & BFS24

[백준] 1707번 이분 그래프 JAVA (자바) 풀이 문제 1707 그래프의 정점의 집합을 둘로 분할 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 이 그래프가 이분 그래프인지 아닌지 판별해라 이분그래프란? 모든 정점을 두가지 색으로 표현 인접한 정점을 연결할 때에는 무조건 다른 색상의 것을 연결 (예시) [입력] : 첫째 줄에 테스트 케이스의 개수 K : 각 테스트 케이스, 첫째 줄에는 정점의 개수 V와 간선의 개수 E (공백으로 구분) (각 정점 = 1 ~ V까지 차례로 번호 부여) : 각 테스트 케이스, 둘째 줄부터 연결된 정점 u, v 2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2 → 테스트 케이스 2개 → 1번 케이스) 정점 3개 / 간선은 2개 → 정점 = .. 2024. 1. 23.
[백준] 10026번 적록색약 JAVA (자바) 풀이 문제 10026 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다 구역은 같은 색으로 이루어져 있다 같은 색상이 상하좌우로 인접해 있는 경우 같은 구역으로 취급 적록색약인 사람은 초록과 빨강은 같은 색으로 보여진다 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구해라 (예시) RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람 : 구역 총 4개 (빨강 2, 파랑 1, 초록 1) 적록색약인 사람은 : 구역 총 3개 볼 수 있다. (빨강 & 초록 2, 파랑 1) [입력] : 첫째 줄에 N (1 ≤ N ≤ 100) : 둘째 줄부터 N개 줄에는 그림 5 RRRBB GGBBB BBBRR BBRRR RRRRR [출력] : 적록.. 2024. 1. 22.
[백준] 2468번 안전 영역 JAVA (자바) 풀이 문제 2468 (dfs, 백트래킹)지역의 높이 정보를 파악지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정각 지역의 높이 정보 = N크기의 2차원 배열 형태배열의 각 원소 = 높이 침수 정도를 어떤 높이로 설정해야 안전한 영역이 최대가 되는지 계산해라 예) N=5 → 5 x 5 배열 6826232346673327253689527 높이가 4 이하인 지점 물에 잠겼다 = 회색6826232346673327253689527 →  안전한 영역 = 물에 잠기지 않는 지점 상, 하, 좌, 우로 인접하며 그 크기가 최대인 영역→  안전한 영역 = 5개 높이가 6이하인 지점이 잠긴다면 안전.. 2024. 1. 22.
[백준] 2210번 숫자판 점프 JAVA (자바) 풀이 문제 2210번 : 5 x 5의 숫자판 존재 각 칸에는 0~9까지의 숫자가 들어갈 수 있다 : 처음 칸에서 5번 더 이동 가능 (상하좌우로만) 모두 이동한 칸은 처음 칸을 포함해서 총 6칸 중복으로 이동 가능 (즉 갔던 자리 다시 갈 수 있다는 뜻) : 나올 수 있는 6칸의 숫자를 붙여서 6자리의 경우의 수를 구하여라 [입력] : 다섯 개의 줄에 다섯 개의 정수로 숫자판 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 [출력] : 경우의 수 출력 15 [문제접근] 모든 경로를 하나하나 다 파악해줘야 하기 때문에 DFS 선택! 다른 문제와 달리 방문기록을 표시하는 객체가 없다 → 해당 문제는 중복을 허용하기 때문이다 → 즉, 같은 자리를 다시 찾아갈 수 있다 다만 .. 2024. 1. 21.
[백준] 7576번 토마토 JAVA (자바) 풀이 문제 7576번 (2차원 토마토 문제) : 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 구하는 프로그램 : 토마토는 격자모양 상자의 칸에 하나씩 넣은 다음 상자들을 수직으로 쌓아 올려서 창고에 보관 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다 : 익은 토마토과 인접하면 익지 않은 토마토들 영향을 받는다 인접한 곳 = 상, 하, 좌, 우 4가지 방향에 있는 토마토 [입력] : 첫 줄에는 상자 가로크기 M, 상자 세로 크기 N : 둘째 줄부터는 저장된 토마토들의 가로 세로 정보 : 1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 들어있지 않은 칸 [출력] : 여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력 : 저장될 때부터 모든 토마토가 익어있.. 2023. 9. 21.
[백준] 7569번 토마토 JAVA (자바) 풀이 문제 7569번 (3차원 토마토 문제) : 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 구하는 프로그램 : 토마토는 격자모양 상자의 칸에 하나씩 넣은 다음 상자들을 수직으로 쌓아 올려서 창고에 보관 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다 : 익은 토마토과 인접하면 익지 않은 토마토들 영향을 받는다 인접한 곳 = 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토 [입력] : 첫 줄에는 상자 가로크기 M, 상자 세로 크기 N, 쌓아올려지는 상자의 수 H (단, 2 ≤ M,N ≤ 100, 1 ≤ H ≤ 100) : 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보 : 1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 들어있지 .. 2023. 9. 21.
[백준] 11725번 트리의 부모 찾기 JAVA (자바) 풀이 문제 11725번 :  트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램     [입력] :  첫째 줄에 노드의 개수 N :  둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점   [출력] :  2 부터 N 노드까지 부모 노드 순서대로 출력    DFS  현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 Stack 혹은 재귀함수로 구현 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가더 이상 갈 수 없게되면 다른 방향으로 다시 탐색 진행모든 노드를 방문하는 경우에 사용  ArrayList   - 본 코드에 arr 가 아닌 arraylist를 사용한 이유는 메모리초과 때문이다 - 배열과 차이점 : 배열은 크기가 고정, ArrayList는 크기가 가변적   - Arr.. 2023. 9. 20.
[백준] 7562번 나이트의 이동 JAVA (자바) 풀이 문제 7562번 (bfs) :  나이트는 몇 번 움직이면 칸으로 이동할 수 있을까?    [입력] :  첫째 줄에는 테스트 케이스 묶음 개수  :  테스트 케이스 한묶음 당 3개의 줄이 있다 :  첫째 줄에는 체스판의 한 변의 길이 (크기 1 × 1) :  둘째 줄에는 나이트가 현재있는 칸 위치 :  셋째 줄에는 나이트가 이동하려는 칸 위치   [출력] :  각 테스트 케이스 묶음마다 나이트의 최소 이동 횟수 출력   [설명]  BFS    현재 정점에 연결된 가까운 점들부터 탐색  Queue를 사용해서 구현     java.awt.Point  -  Point 클래스는 좌표 상의 위치를 나타내는데 사용-  x와 y좌표값을 저장하기 위한 멤버변수를 갖는다 Field SummaryModifier and Ty.. 2023. 9. 17.
[백준] 11724번 연결 요소의 개 JAVA (자바) 풀이 문제 11724번 : 연결 요소의 개수 구하기 [입력] : 첫째 줄에 정점의 개수 N, 간선의 개수 M : 둘째 줄부터 M개의 줄에 간선의 양 끝점 u, v(1 ≤ u, v ≤ N, u ≠ v) (같은 간선은 한 번만) [출력] : 연결 요소의 개수를 출력 [설명] DFS 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 Stack 혹은 재귀함수로 구현 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색 진행 모든 노드를 방문하는 경우에 사용 [문제 과정] 입력 1 2 2 5 5 1 3 4 4 6 출력 2 출처 : https://aeunhi99.tistory.com/59 if(!visit[i]){ dfs(i); } → if문 시작 dfs(1).. 2023. 9. 16.
[백준] 4963번 섬의 개수 JAVA (자바) 풀이 문제 4963번 : 섬의 개수를 세는 프로그램 : 정사각형으로 이루어져 있는 섬과 바다 지도 : 붙어있는 땅이면 가로, 세로, 대각선 이동가능 = 하나의 섬 섬 개수 = 3 [입력] : 너비 w, 높이 h : h개 줄만큼 지도 표시 (1 = 땅, 0 = 바다) : 위의 과정 반복 : 맨 마지막 줄에는 0 0 [출력] : 각 테스트 케이스의 섬의 개수를 출력 [설명] BFS 현재 정점에 연결된 가까운 점들부터 탐색 Queue를 사용해서 구현 java.awt.Point - Point 클래스는 좌표 상의 위치를 나타내는데 사용 - x와 y좌표값을 저장하기 위한 멤버변수를 갖는다 Field Summary Modifier and Type Field and Description 설명 int x x좌표 int y y.. 2023. 9. 15.

티스토리툴바