본문 바로가기

전체 글364

백준 7576번 - 토마토[BFS/Java] 문제 설명철수의 토마토 농장에는 여러 상자에 토마토가 보관되어 있다. 상자의 크기는 N×M 크기의 격자 형태로 구성되며, 각 칸에는 익은 토마토(1), 익지 않은 토마토(0), 또는 빈 칸(-1)이 존재할 수 있다. 하루가 지나면 익은 토마토는 인접한 네 방향(상, 하, 좌, 우)에 있는 익지 않은 토마토를 익게 만든다. 모든 토마토가 익는 데 걸리는 최소 일수를 계산해야 한다. 만약 익지 않은 토마토가 존재하나, 모두 익지 못하는 경우 -1을 출력하고, 처음부터 모든 토마토가 익어 있으면 0을 출력한다. 문제 접근이 문제는 최단 거리 탐색 문제로, 너비 우선 탐색(BFS, Breadth-First Search)를 통해 풀 수 있다. BFS는 시작점에서 가까운 노드부터 차례대로 탐색하는 방법으로, 인접한.. 2024. 10. 19.
미로의 최단거리 통로(BFS) 7x7 격자판 미로를 탈출하는 최단경로의 길이를 구하는 문제를 해결하기 위해 BFS(너비 우선 탐색) 알고리즘을 사용한다. BFS는 출발점에서 도착점까지 도달할 수 있는 모든 경로를 '너비'로 확장해 나가며 최단 경로를 구하는 알고리즘이다. 문제 설명격자판의 좌표 (1, 1)에서 출발하여 (7, 7)에 도착하는 최단 경로의 길이를 출력한다. 격자판의 각 칸은 벽(1) 또는 도로(0)로 이루어져 있으며, 이동할 수 있는 방향은 상, 하, 좌, 우로 한 칸씩 이동한다. 도착점에 도달할 수 없는 경우 -1을 출력한다.위 미로에서 최단 경로는 총 12칸을 이동한 것이다. 예시 입력0 0 0 0 0 0 00 1 1 1 1 1 00 0 0 1 0 0 01 1 0 1 0 1 11 1 0 1 0 0 01 0 0 0 1.. 2024. 10. 19.
미로탐색(DFS) 이 문제는 7x7 격자판에서 주어진 출발점에서 도착점까지 갈 수 있는 경로의 개수를 구하는 문제다. 격자판에서 1은 벽을 나타내고, 0은 통로를 나타낸다. 상하좌우로만 이동할 수 있으며, 중복되지 않는 경로를 찾아야 한다. 1. 문제 설명출발점: (1, 1) 좌표도착점: (7, 7) 좌표벽은 1로 표시되며, 통로는 0으로 표시됨상하좌우로만 이동 가능경로의 수를 구하는 문제2. 입력 및 출력입력: 7x7 격자판의 정보가 주어진다. 1은 벽, 0은 통로다.출력: 출발점에서 도착점까지 가능한 경로의 개수를 출력한다.3. 예제입력 예제:0 0 0 0 0 0 00 1 1 1 1 1 00 0 0 1 0 0 01 1 0 1 0 1 11 1 0 0 0 0 11 1 0 1 1 0 01 0 0 0 0 0 0 출력 예제:8.. 2024. 10. 19.
수열 추측하기(DFS) 이 문제는 파스칼의 삼각형과 조합을 이용하여, 주어진 N과 마지막 값 F를 기반으로 가장 윗줄에 들어갈 숫자들을 구하는 문제다. 입력으로 주어지는 N과 F는 각각 삼각형의 가장 윗줄에 위치한 숫자의 개수와 마지막 줄에 나오는 값이다. 1. 문제 설명주어진 N개의 숫자를 파스칼의 삼각형처럼 계산하여, 그 밑줄에 있는 숫자가 주어진 F가 되는 가장 윗줄의 숫자들을 구하는 것이 문제다. 만약 답이 여러 가지가 나올 경우, 사전순으로 가장 앞서는 경우를 출력해야 한다. 2. 파스칼의 삼각형과 가중치파스칼의 삼각형은 아래와 같이 계산되며, 각 숫자가 그 아래 숫자에 얼마나 기여하는지를 이항계수로 계산할 수 있다.예를 들어, n = 4, 그리고 주어진 윗줄이 3 1 2 4라면 다음과 같은 삼각형이 만들어진다.이 삼.. 2024. 10. 19.
조합의 경우수(메모이제이션) 1. 문제 설명조합의 경우수는 일반적으로 다음과 같은 공식을 이용해 계산한다.하지만 이 공식 대신 재귀와 메모이제이션을 활용한 방식으로 조합수를 구하는 프로그램을 작성해보자. 2. 공식조합수는 다음과 같은 재귀적 성질을 가진다.즉, n개의 원소에서 r개를 선택하는 경우는 n-1개의 원소에서 r-1개를 선택하는 경우와 n-1개의 원소에서 r개를 선택하는 경우의 합으로 계산된다.이 공식에 따라 재귀를 이용하여 조합수를 구할 수 있다. 3. 입력첫째 줄에 자연수 n(3 ≤ n ≤ 33)과 r(0 ≤ r ≤ n)이 주어진다. 4. 출력첫째 줄에 조합수를 출력한다. 5. 코드 설명package com.example.codingtest;import java.io.BufferedReader;import java.io.. 2024. 10. 18.
순열 구하기(DFS) 설명10 이하의 N개의 자연수가 주어졌을 때, 이 중 M개를 뽑아 일렬로 나열하는 모든 경우의 수(순열)를 출력하는 문제이다. 이때 출력은 사전순으로 오름차순으로 정렬된 결과를 제공해야 한다. 입력 설명첫 번째 줄에 자연수 N(3두 번째 줄에 N개의 자연수가 오름차순으로 주어진다.출력 설명첫 번째 줄에 모든 경우의 순열을 출력한다.출력되는 순서는 사전순으로 오름차순이다.예시 입력3 23 6 9  예시 출력3 63 96 36 99 39 6 풀이 과정입력된 자연수 배열에서 M개를 선택해 순서대로 나열하는 순열을 구한다.DFS(깊이 우선 탐색) 방법을 이용하여 순열을 구하며, 선택된 숫자가 다시 선택되지 않도록 체크 배열을 사용한다.모든 경우의 순열을 탐색하여 조건을 만족하면 출력한다.D(0)├── i = 0.. 2024. 10. 18.

티스토리툴바