본문 바로가기

코딩테스트 준비627

[백준] 15653번 - 구슬 탈출 4 [Java] https://www.acmicpc.net/problem/15653 1.  아이디어 기존 구슬 탈출 2 문제에서 이제 구슬이 탈출할 수 있을 때까지 시도하고 불가능한 경우면 -1을 출력하는 문제로 dist가 10 초과면 -1d을 출력하던 조건만 없애면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 13460번 - 구슬 탈출 2 [Java])2. 문제풀이 아이디어 그대로 해당 라인만 수정했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final char[] order = {'U', 'D', 'L', 'R'}; private static class Point { int r;.. 2025. 1. 17.
[백준] 15644번 - 구슬 탈출 3 [Java] https://www.acmicpc.net/problem/15644 1.  아이디어 기존 구슬 탈출 2 문제에서 경로에 대한 출력이 추가된 문제로 경로를 기록하는 Queue를 활용해서 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 13460번 - 구슬 탈출 2 [Java])2. 문제풀이 기존 BFS에서 경로를 기록하기 위해 StringBuilder를 담는 Queue를 만들었다. 이후 BFS에서 새 구슬 위치를 추가할 때 새 경로도 같이 넣고 정답 반환 시 경로도 같이 반환하도록 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final char[] order = {'U', 'D', 'L', .. 2025. 1. 17.
[백준] 13460번 - 구슬 탈출 2 [Java] https://www.acmicpc.net/problem/13460 1.  아이디어 기존 구슬 탈출 문제에서 횟수에 대한 출력으로 변경된 문제로 동일하게 BFS를 통한 시뮬레이션으로 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 13459번 - 구슬 탈출 [Java])2. 문제풀이 기존 BFS에서 1을 반환하던걸 dist를 반환하고 0 대신 -1을 반환하면 간단하게 해결할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final char[] order = {'U', 'D', 'L', 'R'}; private static class Point { int r; in.. 2025. 1. 17.
[백준] 13459번 - 구슬 탈출 [Java] https://www.acmicpc.net/problem/13459 1.  아이디어 BFS를 통한 시뮬레이션으로 해결할 수 있다.2. 문제풀이 빨간 구슬, 파란 구슬, 구멍의 위치를 Point 객체에 담아서 관리했다. 객체에 대한 시뮬레이션이라 원본이 변경되지 않는게 중요하다고 생각해서 깊은 복사를 하기도 쉽고 직관적이어서 활용했다.BFS는 Queue에는 빨간 구슬, 파란 구슬을 같이 담고 같이 빼는 방식으로 구현했고 방문 체크는 4차원 배열로 빨간 구슬의 위치와 파란 구슬의 위치를 같이 기록했다. 빨간 구슬의 위치가 일정해도 파란 구슬의 위치가 달라지면 다른 상황이라 같이 기록해야한다.Queue가 빌 때까지 BFS를 진행하는데 두 구슬을 같이 넣었으니 같이 빼서 다루고 빨간 구슬이 구멍에 위치하고 파란.. 2025. 1. 17.
[백준] 1926번 - 그림 [Java] https://www.acmicpc.net/problem/1926 1.  아이디어 BFS와 DFS를 활용해서 간단하게 해결할 수 있다.2. 문제풀이 입력을 받은 후 2중 for문으로 도화지를 순회하며 그림을 발견하면 BFS 또는 DFS 알고리즘으로 그림의 크기를 구했다. 이후 개수를 세주고 그림의 최대 크기를 저장하는 max 변수와 비교 갱신하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { private static final int[] dr = {-1, 0, 1, 0}; private static final int[] dc = {0, 1, 0, -1}; public static void main(.. 2025. 1. 17.
[백준] 2667번 - 단지번호붙이기 [Java] https://www.acmicpc.net/problem/2667 1.  아이디어 단지를 하나의 그래프로 생각해서 BFS와 DFS를 활용해서 해결했다.2. 문제풀이 입력을 받은 후 2중 for문으로 지도를 순회하며 집을 발견하면 BFS 또는 DFS로 연결된 다른 집을 모두 탐색하며 개수를 세면 단지 하나에 포함된 집의 수를 셀 수 있다. 같은 집을 방문하지 않게 방문 체크를 하며 진행했고, 단지마다 구한 집의 수는 우선순위 큐에 넣어서 정렬한 채로 출력하도록 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { private static final int[] dr = {-1, 0, 1, 0}; private static .. 2025. 1. 17.
[백준] 2606번 - 바이러스 [Java] https://www.acmicpc.net/problem/2606 1.  아이디어 BFS와 DFS 알고리즘으로 해결했다.2. 문제풀이 컴퓨터와 네트워크가 정점과 간선이 되는 그래프로 해석할 수 있고 1번 컴퓨터가 바이러스를 옮기는 것은 1번 정점에 연결된 다른 정점의 수를 구하는 것과 동일하다. 1번 컴퓨터를 제외하고 세는 것만 주의해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.. 2025. 1. 17.
[백준] 7562번 - 나이트의 이동 [Java] https://www.acmicpc.net/problem/7562 1.  아이디어 최단거리를 구하는 문제로 BFS를 활용하면 해결할 수 있다.2. 문제풀이 2차원 배열과 BFS에서 일반적으로 사용하는 사방탐색 배열 대신 나이트의 이동에 맞게 8칸 이동을 할 수 있게 구현만 하면 됐다. BFS에서 최단 거리는 Queue의 크기를 변수에 담아 해당 변수만큼 반복하면 1칸 이동을 체크할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final int[] dr = {-1, -2, -2, -1, 1, 2, 2, 1}; private static final int[] dc = {-2, -1, 1, 2, 2.. 2025. 1. 17.
[백준] 1260번 - DFS와 BFS [Java] https://www.acmicpc.net/problem/1260 1.  아이디어 문제 이름 그대로 DFS와 BFS로 풀면 된다.2. 문제풀이 DFS와 BFS의 기본 구현을 할 수 있으면 해결할 수 있는 문제로 인접리스트 기반으로 구현했다. 출력을 위해 StringBuilder를 정적 변수로 사용해서 활용했고, 번호가 작은 정점을 우선으로 방문하기 위해 인접리스트를 한번 정렬해줘야 한다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final StringBuilder sb = new StringBuilder(); private static boolean[] visited; public static .. 2025. 1. 17.
[백준] 11724번 - 연결 요소의 개수 [Java] https://www.acmicpc.net/problem/11724 1.  아이디어 주어진 입력으로 만들어질 수 있는 그래프의 개수를 구하는 문제로 BFS, DFS, Union-Find 알고리즘 3가지 방법으로 해결할 수 있었다.2. 문제풀이 BFS와 DFS는 주어진 입력으로 그래프의 연결관계를 나타내는 인접리스트와 각 정점을 방문했는지 표시하는 방문 체크 배열을 만든 후 반복문으로 각 정점을 순회하며 방문한 정점이면 넘어가고 방문하지 않은 정점이면 탐색으로 그래프의 개수를 세는 방식으로 구현했다. Union-Find는 인접리스트를 만드는 대신 바로 집합 연결을 해주었다. 이후 각 정점이 집합의 그룹장인지 여부만 세면 간단하게 그래프의 개수를 구할 수 있다.3. 코드 import java.io.*;im.. 2025. 1. 17.
[백준] 2822번 - 점수 계산 [Java] https://www.acmicpc.net/problem/2822 1.  아이디어 람다식을 활용한 정렬과 방문체크로 해결했다.2. 문제풀이 문제의 점수와 문제의 번호가 전부 필요한 상황이어서 이를 2차원 배열로 처리했다. 문제 점수를 기준으로 정렬해서 5문제의 합을 구했고 5문제의 번호를 boolean 타입 배열에 체크 후 다시 순회하며 StringBuilder에 넣어서 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new.. 2025. 1. 17.
[백준] 13136번 - Do Not Touch Anything [Java] https://www.acmicpc.net/problem/13136 1.  아이디어 몫을 구하는 연산을 활용하면 해결할 수 있다.2. 문제풀이 R * C 크기의 직사각형을 N * N 크기의 정사각형으로 완전히 덮어야하는 상황이다. 이는 R/N, C/N 같은 몫을 구하면 기본적인 개수를 구할 수 있는데 이때 완전히 덮지 못하는 자투리에서 1개씩을 할당해야하므로 N-1을 더한 값을 N으로 나누어서 해결했다. CCTV의 개수가 int형 범위를 넘어갈 수 있음에 주의해야한다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Bu.. 2025. 1. 17.

티스토리툴바