개발 공부~

설명N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.만약 위와 같다면 섬의 개수는 5개입니다.입력첫 번째 줄에 자연수 N(3두 번째 줄부터 격자판 정보가 주어진다.출력첫 번째 줄에 섬의 개수를 출력한다.예시 입력 1 71 1 0 0 0 1 00 1 1 0 1 1 00 1 0 0 0 0 00 0 0 1 0 1 11 1 0 1 1 0 01 0 0 0 1 0 01 0 1 0 1 0 0예시 출력 15  풀이 - DFS 육지를 만나면 정답 증가육지를 처음 만나면 이중for문으로 상하좌우 및 대각선 검사 -> 방문처리는 0으로 값 변경dfs 종료되면 다시 1..

설명현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다.토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면,익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 보관하는 격자모양의 상자들의 크기와 ..

설명7*7 격자판 미로를 탈출하는 최단경로의 길이를 출력하는 프로그램을 작성하세요.경로의 길이는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다.출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다.격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면위와 같은 경로가 최단 경로의 길이는 12이다.입력첫 번째 줄부터 7*7 격자의 정보가 주어집니다.출력첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.예시 입력 1 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 0 01 0 1 0 0 0 0예시 출력 112  내 풀..

설명다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?각 단위의 동전은 무한정 쓸 수 있다.입력첫 번째 줄에는 동전의 종류개수 N(1그 다음줄에 거슬러 줄 금액 M(1출력첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.예시 입력 1 31 2 515예시 출력 13힌트출력 설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다. 내 풀이 - BFS최소 개수를 보고 바로 BFS가 생각났다 1부터 거스름돈 m까지를 인덱스 값으로 갖는 방문 배열 생성큐에는 현재까지의 합을 넣음같은 합을 여러번 계산하지 않고 최단 경로의 합을 구하여 진행 -> 방문배열현재까지의 합을 큐에서 꺼내 입력받은 동전 배열을 순회하며 더한 값이 m이면 L+1 리턴더한 값이 ..

문제 다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요 입력첫째 줄에는 정점의 수 N(1M가 주어진다그 다음부터 줄에 걸쳐 연결 정보가 주어진다 출력1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례대로 출력하세요 입력 예제6 91 31 42 12 53 44 54 66 26 5 출력 예제2 : 33 : 14 : 15 : 26 : 2 내 풀이최단 거리 => BFS1번 정점에서 몇 번만에 갈 수 있는지 -> 이 횟수의 최솟값 구하기   인접리스트로 구현 및 1번 정점에서 각 인덱스 정점까지의 최소 거리를 저장하는 dis 배열 이용  import java.util.ArrayList;import java.util.LinkedList;import java.util.Que..

아래 그림과 같은 이진트리에서 루트 노드 에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하세요.각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선에지의 개수를 길이로 하겠습니다.가장 짧은 길이는 3번 노드까지의 길이인 1 이다  내 풀이 - DFS Math.min(오른쪽 자식, 왼쪽 자식)=> 두 값 중에 가장 짧은 길이를 받아와야함 => 리턴 받는 노드 : 2=> 노드 3은 리턴 값이 1=> 노드 1은 노드 2의 값 2와 노드 3의 값 1중 최솟값으로 노드 3의 값인 1이 정답  import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;class Node{ int data; ..

설명현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.송아지는 움직이지 않고 제자리에 있다.현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.입력첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.출력점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.예시 입력 1 5 14예시 출력 13  내 풀이BFS -> 최단거리 visited[] 배열이미 방문한 ..

아래 그림과 같은 이진트리를 레벨탐색 연습하세요 레벨 탐색 순회 출력 :12 34 5 6 7 내 풀이넓이 우선 탐색: 레벨 0부터 끝까지 같은 레벨에 속한 노드를 왼쪽부터 방문한다즉, 출발점에서 1번에 갈 수 있는 노드들을 다 방문하고 2번만에 갈 수 있는 모든 노드들 탐색하는 순서이다  하나의 레벨이 시작될 때의 큐 사이즈를 len변수에 저장-> len만큼 for문이 돌면서 큐에서 하나 꺼내고 출력-> 꺼낸 노드와 연결된 모든 노드를 큐에 추가-> 하나의 레벨이 끝났으므로 L 하나 증가  import java.util.LinkedList;import java.util.Queue;class Node{ int data; Node lt, rt;//왼쪽, 오른쪽 자식의 주소 public Node(int val..