본문 바로가기

문제풀이/백준83

[JAVA] BOJ 백준 1981번 - 배열에서 이동 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 2. 내가 푼 방법 무작정 (n, n) 위치까지 이동하기보다, (최대 - 최소) 값이 나올 수 있는 경우를 나열한 뒤에 필요한 탐색이 이뤄져야 한다. 투포인터를 사용하기 위해 배열의 모든 숫자가 담긴 list를 정렬한다. s는 0부터, e는 (1, 1) 혹은 (n, n)의 최대 값의 인덱스부터 시작한다. 또한, s.. 2024. 1. 24.
[JAVA] BOJ 백준 2250번 - 트리의 높이와 너비 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 2. 내가 푼 방법 탐색하는 규칙이 존재하는 DFS 문제이다. 루트 노드에서 시작해 각 노드가 위치한 가로 인덱스를 구하기 위해 왼쪽 -> 위 -> 오른쪽 순서로 노드를 탐색한다. 이때 standard 매개변수는 현재 노드보다 더 왼쪽에 위치한 노드의 개수를 의미한다. 따라서 왼쪽 자식 노드를 탐색할 땐 이전에 받은 s.. 2024. 1. 24.
[JAVA] BOJ 백준 9466번 - 텀 프로젝트 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 2. 내가 푼 방법 사이클을 찾아내기 위한 필수 문제라고 생각한다. 이 문제의 핵심은 isDone 변수를 통해 이전에 방문한 적 있는 사람인지 확인하는 것이다. 따라서 사이클을 찾기 위해 텀 프로젝트를 같이 하고 싶은 사람을 타고 들어가면서, 처음 방문하는 경우에는 isVisit 변수를 true로, 두 번째 방문하는 경우에는 isDone 변수.. 2024. 1. 16.
[JAVA] BOJ 백준 16724번 - 피리 부는 사나이 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 2. 내가 푼 방법 나는 SAFE ZONE을 루프로 정의했다. 결국 SAFE ZONE이 수렴해야 하는 특정한 위치이기 때문에, 최소의 SAFE ZONE은 최소 루프 개수를 의미한다. 루프는 두 개의 boolean[][] 배열을 통해 확인할 수 있다. 이전에 만들어진 적 있는 루프에 속하는지 확인하기 위.. 2024. 1. 14.
[JAVA] BOJ 백준 11967번 - 불켜기 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 2. 내가 푼 방법 현재 위치에서 불을 켠 후 이동할 수 있는 곳을 BFS를 이용해 확인하고, 이동할 수 있을 경우에 Queue에 넣어 다시 탐색하는 과정으로 쉽게 풀린다. 하지만 boolean[][] 배열 3개를 이용해 속도를 개선시킨 방법을 설명해보려고 한다. 먼저 N과 light.. 2024. 1. 14.
[JAVA] BOJ 백준 16954번 - 움직이는 미로 탈출 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 2. 내가 푼 방법 캐릭터가 이동하고, 체스판이 움직이는 과정을 탈출할 수 있도록 하는 조건이 제일 관건인 문제라고 생각한다. 먼저 캐릭터가 이동하는 moveCharacter 함수는 BFS 알고리즘을 사용한다. 보통은 for문에서 다음 칸이 벽일 경우에 이동할 수 없는 것만 확인하면 된다. 하지만 이 문제는 체스판이 이동하기 .. 2024. 1. 10.

티스토리툴바