코딩테스트 준비627 [백준] 2583번 - 영역 구하기 [Java] https://www.acmicpc.net/problem/2583 1. 아이디어 BFS 알고리즘과 DFS 알고리즘으로 간단하게 해결할 수 있다.2. 문제풀이 주어진 정보를 통해 직사각형이 그려진 부분은 true, 그려지지 않은 부분은 false로 표현하는 boolean 타입 2차원 배열로 모눈종이를 표현했다. 이후 모눈종이를 순회하며 false인 곳을 발견하면 BFS, DFS로 인접한 곳의 개수를 세며 true로 바꿔줬다. 원본을 수정하며 방문체크 처리를 했고 센 개수는 우선순위 큐에 넣어서 오름차순으로 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { private static final int[] d.. 2025. 1. 21. [백준] 1012번 - 유기농 배추 [Java] https://www.acmicpc.net/problem/1012 1. 아이디어 전체 땅에서 인접한 배추들을 묶은 배추 묶음의 개수를 구하는 문제로 BFS 알고리즘과 DFS 알고리즘으로 해결할 수 있다.2. 문제풀이 배추가 있는 땅은 true, 없는 땅은 false로 표현하는 boolean 타입 2차원 배열로 땅을 표현했다. 이후 땅을 순회하며 배추가 있는 땅을 발견하면 BFS, DFS로 배추가 있는 땅을 전부 false로 바꾸는 방식으로 해결했다. 원본 맵을 바꾸는 방식으로 방문 체크까지 같이 처리했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { private static final int[] dr = {-1, 0, 1, .. 2025. 1. 21. [백준] 5567번 - 결혼식 [Java] https://www.acmicpc.net/problem/5567 1. 아이디어 최단거리를 구하는 BFS 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 동기들의 친구 관계가 주어졌을 때 상근이를 기준으로 친구의 친구까지 찾아야하는 문제이다. 최단거리를 구하는 BFS 알고리즘을 활용해서 거리 2까지 친구들을 찾는 방식으로 구현했다. 동기의 수와 친구 관계가 많이 주어져서 인접리스트를 활용해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR.. 2025. 1. 21. [백준] 12869번 - 뮤탈리스크 [Java] https://www.acmicpc.net/problem/12869 1. 아이디어 BFS, DFS, 다이나믹 프로그래밍 3가지 방법을 활용해서 해결했다.2. 문제풀이 SCV는 몇 개가 주어지든 3개로 맞춰서 배열에 담았다. 3개 미만으로 주어지면 체력 0의 유령 SCV라고 가정했다. 이는 이후 풀이에서 SCV가 파괴된 경우도 동일하다. 뮤탈리스크의 공격은 9-3-1로 들어오는데 이 공격이 SCV에게 들어오는 것은 순열로 6가지 경우가 있고 각 SCV 상태에 대해 6가지 공격 조합이 추가된다는 흐름으로 구현했다. 공통적으로 현재 상태와 조합을 통해 다음 체력 상태를 반환하는 hit 메서드와 공격 조합에 대한 탐색배열을 작성했고 SCV 체력이 음수가 되지 않게 하여 방문 체크를 진행했다. SCV의 체력은 .. 2025. 1. 21. [백준] 5014번 - 스타트링크 [Java] https://www.acmicpc.net/problem/5014 1. 아이디어 BFS 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 현재 위치 S에서 G까지 가야하는데 위로 U, 아래로 D만큼 이동하는 상황의 반복으로 G를 가야한다. 이는 S를 시작으로 현재위치 C에 대해 C + U, C - D 위치가 다음 위치가 되고 다시 다음 위치에서 +U, -D를 반복하는 상황으로 최단 거리를 구하는 BFS와 동일한 로직이다. 이를 활용해 다음 위치가 건물 내 위치면서 방문한 적이 없으면 방문하는 BFS로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) .. 2025. 1. 20. [백준] 1600번 - 말이 되고픈 원숭이 [Java] https://www.acmicpc.net/problem/1600 1. 아이디어 각 이동 방법에 대한 2가지 탐색 배열과 방문 체크처리를 통해 해결할 수 있다.2. 문제풀이 각 위치에서 원숭이의 이동 방법과 말의 이동 방법 모두 가능하므로 2가지 이동 방법에 대한 탐색 배열을 각각 만들어서 각각 반복문으로 새 위치를 생성해서 사용했다. 원숭이의 이동 방법의 경우 일반적인 4방 탐색으로 진행하며 말의 이동 방법은 해당 위치를 담은 8방 탐색으로 진행했다. 방문 체크의 경우 말의 이동 방법을 몇 번 사용해서 온 위치인지까지 기록해야해서 3차원 boolean 타입 배열을 통해 위치와 이동 방법까지 저장한 방법과 2차원 int 타입 배열로 위치에 이동 방법을 저장한 두 가지 케이스로 해결했다.3. 코드 imp.. 2025. 1. 20. [백준] 16946번 - 벽 부수고 이동하기 4 [Java] https://www.acmicpc.net/problem/16946 1. 아이디어 각 위치에서 해당 벽을 부쉈을 때 이동할 수 있는 칸 즉 0의 개수를 세는 문제로 BFS를 활용하면 해결할 수 있다.2. 문제풀이 기본 흐름은 입력을 받아서 2차원 배열로 맵을 표현한 후 BFS를 돌았다. BFS는 이동할 수 있는 칸을 발견하면 연결된 모든 이동할 수 있는 칸의 개수를 세서 경계가 됐던 벽에 더해주는 방식으로 구현했다. 이를 위해 두 개의 Queue를 활용해서 하나는 이동할 수 있는 칸, 하나는 경계가 되는 벽들을 넣었고 둘 다 같은 방문 체크 배열로 방문 체크를 해줬다. 이동할 수 있는 칸에 대한 BFS로 이동할 수 있는 칸의 개수를 세주며 경계를 만나면 경계는 따로 Queue에 넣어줬고, 이후 경계를 .. 2025. 1. 20. [백준] 16933번 - 벽 부수고 이동하기 3 [Java] https://www.acmicpc.net/problem/16933 1. 아이디어 이전 벽 부수고 이동하기 2 문제에서 벽을 낮에만 부술 수 있는 조건이 추가된 문제로 낮과 밤은 BFS에서 구하고 있는 최단거리를 통해 알아낼 수 있다.2. 문제풀이 최단거리를 저장한 dist 변수는 첫 칸부터 센다는 조건에서 1로 시작하며 현재 낮이다. 이를 통해 dist가 홀수면 낮, 짝수면 밤이 된다. 기존 로직에서 벽을 부수는 상황에서 낮인지 밤인지만 조건문으로 확인해서 낮이면 동일하게 벽을 부수고 밤일 경우 낮이 될 때까지 기다려야하므로 방금 뽑은 노드를 다시 Queue에 넣어주면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { privat.. 2025. 1. 20. [백준] 14442번 - 벽 부수고 이동하기 2 [Java] https://www.acmicpc.net/problem/14442 1. 아이디어 이전 벽 부수고 이동하기 문제에서 벽을 부술 수 있는 횟수가 1회에서 최대 K회로 바뀐 문제로 방문 체크 단계에서 K회까지 적용 가능하게 좀만 수정해주면 된다.([코딩테스트 준비/백준] - [백준] 2206번 - 벽 부수고 이동하기 [Java])2. 문제풀이 이전 문제와 동일한 로직으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node { int r; int c; int cntBrokenWall; public Node(int r, int c, int c.. 2025. 1. 20. [백준] 2206번 - 벽 부수고 이동하기 [Java] https://www.acmicpc.net/problem/2206 1. 아이디어 최단거리를 구하는 일반적인 BFS에서 벽을 부수고 이동할 수 있는 조건이 추가된 문제로 방문 체크를 고도화하면 해결할 수 있다.2. 문제풀이 방문 체크는 3차원 boolean 타입 배열과 2차원 int 타입 배열 두 가지를 활용했다. 3차원 boolean 타입 배열은 [행][열][벽을 부순 횟수] 이렇게 기록을 하는 방문 체크로 같은 위치를 같은 벽을 부순 횟수로 방문했는지까지 체크를 한다. 다음 칸이 이동할 수 있는 칸이면 해당 칸을 벽을 부순 횟수까지 일치하게 방문한 적이 있는지 체크하고 없으면 방문을 한다. 다음 칸이 벽이면 현재 벽을 부순 적이 있는지 체크하고 벽을 부순 적이 없으면 벽을 부수고 방문 처리를 한다. .. 2025. 1. 20. [백준] 1302번 - 베스트셀러 [Java] https://www.acmicpc.net/problem/1302 1. 아이디어 HashMap을 활용해 책의 이름과 책의 개수를 다루면 간단하게 해결할 수 있다.2. 문제풀이 key에 책의 이름, value에 책의 개수를 저장하는 HashMap을 만들었다. 이후 반복문으로 Entry를 꺼내서 value가 최대일 때 책의 이름을 얻는 방식으로 구현했고 value가 현재까지 찾은 최댓값과 동일하면 사전순으로 앞서는 것을 비교하기 위해 String의 compareTo 메서드를 활용했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 1. 20. [백준] 10821번 - 정수의 개수 [Java] https://www.acmicpc.net/problem/10821 1. 아이디어 StringTokenizer를 활용한 파싱으로 간단하게 해결할 수 있다.2. 문제풀이 정수를 쉼표로 구분하므로 쉼표를 구분자로 파싱하면 StringTokenizer 객체의 크기가 정수의 개수가 된다. countTokens 메서드로 토큰의 개수를 간단하게 알 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in.. 2025. 1. 20. 이전 1 ··· 15 16 17 18 19 20 21 ··· 53 다음
