본문 바로가기

알고리즘 문제87

[백준] 1600번: 말이 되고픈 원숭이 (Java) 1. 문제설명 그림은 말의 이동방법을 나타낸다. x 표시한 곳으로 말이 갈 수 있다. 말은 장애물을 뛰어넘을 수 있다. 원숭이는 인접한(상하좌우) 칸으로 이동할 수 있고, 말의 이동방법으로 K번만 움직일 수 있다. 모든 이동은 한 번의 동작으로 친다.원숭이가 격자판의 맨 왼쪽 위에서 맨 오른쪽 아래까지 이동할 때, 동작수의 최솟값을 구하는 문제이다.  시간 제한: 2초메모리 제한: 256MB 2. 접근 방식⇒ 이동하는 동작 수의 최솟값 구하기 → BFS원숭이의 이동 경우를 저장하는 dx1, dy1 배열과 말의 이동 경우를 저장하는dx2, dy2 배열을 사용한다.격자판 (0, 0) 위치에서 BFS 탐색을 시작한다.원숭이의 이동 방법(상하좌우)을 사용하여 인접한 4방향으로 이동을 시도한다.말의 이동 방법을 .. 2024. 8. 24.
[백준] 14620번: 꽃길 (Java) 1. 문제설명씨앗은 꽃을 심고나면 1년 후에 꽃이 핀다. 꽃의 씨앗은 세 개밖에 없으므로 세 개의 꽃이 하나도 죽지 않고 1년 후에 꽃잎이 만개하게 한다. 꽃밭은 N*N의 격자 모양이고 씨앗은 (1,1)~(N,N)의 지점 중 한 곳에 심을 수 있으며 꽃이 피면 격자 모양의 위치를 차지한다. 꽃은 다른 꽃잎 또는 꽃술과 닿게 될 경우 두 꽃 모두 죽고, 화단 밖으로 나갈 경우도 꽃이 죽게 된다.화단의 지점 당 가격이 주어지고, 세 개의 씨앗이 모두 꽃이 피게 하는 최소 비용을 구하는 문제이다.시간 제한: 2초메모리 제한: 256MB 2. 접근 방식DFS를 사용하여 3개의 꽃을 심을 수 있는 위치를 탐색한다.꽃을 심을 위치를 선택할 때, 꽃과 꽃잎이 차지하는 위치를 방문하지 않았는지 확인한다.만약 3개의 꽃.. 2024. 8. 24.
[백준] 2146번: 다리 만들기 (Java) 1. 문제설명  NxN 크기의 이차원 평면상에 나라가 존재한다. 이 나라는 여러 섬으로 이루어져 있다. 육지가 없는 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다.두 대륙을 연결하는 가장 짧은 다리 하나를 구하는 문제이다. (길이 구하기)   시간 제한: 2초메모리 제한: 192MB 2. 접근 방식섬 구분 → BFS를 사용하여 각 섬에 번호를 부여한다.최소 다리 길이 계산BFS를 사용하여 각 섬에서 다른 섬까지의 최단 거리를 계산한다.바다인 곳으로 확장하면서 다른 섬에 도달할 때까지의 거리를 구하고, 이 중 짧은 거리를 찾는다. 3. 최종 코드import java.io.*;import java.util.*;public class Main { static int n; // 지도의 크기 .. 2024. 8. 23.
[백준] 7562번: 나이트의 이동 (Java) 1. 문제설명  왼쪽 그림은 체스판에서 나이트가 한 번에 이동할 수 있는 칸이다.현재 나이트가 있는 칸, 나이트가 이동하려고 하는 칸이 주어졌을 때, 나이트가 몇 번의 움직임으로 목표 칸에 도달할 수 있는지 구하는 문제이다.   시간 제한: 1초메모리 제한: 256MB 2. 접근 방식나이트가 현재 있는 칸 부터 BFS를 수행한다.나이트가 이동할 수 있는 칸으로 탐색하고, 이동하는 위치에 현재 위치까지의 거리 + 1을 저장한다.목표 지점에 도달하면 해당 칸의 거리를 출력한다.  3. 최종 코드import java.io.*;import java.util.*;public class Main { static int l; // 체스판 한 변의 길이 static int[][] board; // 체스판 .. 2024. 8. 23.
[백준] 2206번: 벽 부수고 이동하기 (Java) 1. 문제설명NxM의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 곳을 나타낸다. (1, 1)에서 (N, M)까지 이동할 때 최단 경로로 이동하려 한다. 만약 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 더 짧은 경로가 된다면, 벽을 한 개까지 부수는 것이 허용된다.주어진 맵에서 최단 경로를 구하는 문제이다.시간 제한: 2초메모리 제한: 192MB 2. 접근 방식⇒ 최단 거리를 찾는 문제이기 때문에 BFS 문제이지만, 벽을 한 번 부수는 것을 허용하는 조건 때문에 한 번의 BFS로 해결할 수 없다.각 위치에서 벽을 부수지 않은 상태와 벽을 부순 상태를 모두 고려해야 한다.`visited[i][j][0]`: (x, y) 위치에 벽을 부수지 않은 상태로 방문했는지`visit.. 2024. 8. 21.
[백준] 16234번: 인구 이동 (Java) 1. 문제설명NxN 크기의 땅이 있고, 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 인구 이동은 하루동안 아래와 같이 진행되고, 더이상 인구 이동이 없을 때까지 지속된다.각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 문제이다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식while문으로 인구 이동이 일어났는지 확인하고, 더 이상 인구 이동이 발생하지 않을 때까지 반복한다.매 반복 시작 시, 방문 여부 확인하는 배열(`visited`)를 초기화하고, 모든 나라에 대해 방문하지 않은 경우 BFS 탐색한다.인접한 나라와의 인구 차이가 조건에 부합하면큐에 해당 위치를 넣고 방문 처리.. 2024. 8. 21.
[백준] 13023번: ABCDE (Java) 1. 문제설명N명의 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.친구 관계가 주어질 때, 조건에 맞는 친구 관계가 존재하는지 구하는 문제이다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식인접 리스트 형태로 친구 관계를 저장한다.DFS를 사용해 각 노드로부터 시작해서 5명의 친구 관계가 나올 수 있는지 확인한다.DFS에서 방문한 노드를 확인하기 위해 `visited` 배열을 사용한다. 이때 DFS를 호출하고 난 후, 방문 처리한 것을 되돌린다. (백트래킹) 3. 틀린 이유인접 행렬을 사용해서 “시간 초과”가 나왔다.⇒ 인접 리스트를 사용하는 방식을 사용했다. 4. 최종 코드import java.io.*;import java.util.*;public class Mai.. 2024. 8. 20.
반응형