본문 바로가기

Baekjoon/[5] DFS & BFS35

[백준] 2178번 미로 탐색 JAVA (자바) 풀이 문제 2178(BFS)  : N×M크기 미로 101111101010101011111011: 1 = 이동할 수 있는 칸  0 = 이동할 수 없는 칸 : (1, 1) ~ (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구해라  서로 인접한 칸으로만 이동할 수 있고 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다  [입력] :  첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 100) :  다음 N개의 줄에는 M개의 정수로 미로   [출력] :  첫째 줄에 지나야 하는 최소의 칸 수를 출력     [문제접근] 좌표 사용 시 int[] 나 Point 사용→ int[] 배열을 사용Queue q = new LinkedList();q.add(new int[] {x,y});→ Point 사용import.. 2024. 6. 4.
[백준] 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 (DFS, BFS) 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다구역은 같은 색으로 이루어져 있다같은 색상이 상하좌우로 인접해 있는 경우 같은 구역으로 취급적록색약인 사람은 초록과 빨강은 같은 색으로 보여진다 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구해라 (예시) RRRBBGGBBBBBBRRBBRRRRRRRR  적록색약이 아닌 사람 : 구역 총 4개 (빨강 2, 파랑 1, 초록 1) 적록색약인 사람은 : 구역 총 3개 볼 수 있다. (빨강 & 초록 2, 파랑 1) [입력] :  첫째 줄에 N (1 ≤ N ≤ 100) :  둘째 줄부터 N개 줄에는 그림5RRRBBGGBBBBBBRRBBRRRRRRRR   [출력] :.. 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번 (bfs, 3차원 토마토 문제) :  토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 구하는 프로그램 :  토마토는 격자모양 상자의 칸에 하나씩 넣은 다음 상자들을 수직으로 쌓아 올려서 창고에 보관    상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다 :  익은 토마토과 인접하면 익지 않은 토마토들 영향을 받는다    인접한 곳 = 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토     [입력] :  첫 줄에는 상자 가로크기 M, 상자 세로 크기 N, 쌓아올려지는 상자의 수 H (단, 2 ≤ M,N ≤ 100, 1 ≤ H ≤ 100)  :  둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보  :  1 = 익은 토마토, 0 = 익지 .. 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.

티스토리툴바