[BOJ] 1194 달이 차오른다, 가자. (Java)

1. 문제 링크 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 2. 접근법 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 문제이므로 BFS 탐색을 하자 획득한 열쇠의 경우의 수에 따라서 방문 처리를 다르게 해줘야 함 그렇다면 어떻게 획득한 열쇠를 저장할 것인지, 방문 처리를 어떻게 할 것인지 가 포인트 비트마스킹을 활용하자! 1. 변수 선언 열쇠는 A부터 F까지 총 6 종류이므로 2^6의 경우의 수가 생김 Poi..

• format_list_bulleted Algorithm
• · 2023. 9. 27.
• textsms

[BOJ] 17136 색종이 붙이기 (Java)

1. 문제 링크 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 2. 접근법 1. 변수 선언 cntOne: 1이 적힌 칸의 개수 (1이 적힌 모든 칸을 방문했는지의 여부를 판단하기 위해) numOfPapers[]: 색종이 사이즈당 남은 색종이의 수 board[][]: 입력 2. backTracking(int depth) 색종이를 붙일 때마다 depth 증가 즉, depth가 붙인 색종이의 수이므로 최솟값을 담은 ans와 비교하여 dep..

• format_list_bulleted Algorithm
• · 2023. 7. 31.
• textsms

[BOJ] 16637 괄호 추가하기 (Java)

1. 문제 링크 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 2. 접근법 1. 입력받은 수식을 수와 연산자로 나누어 주었다. numbers 리스트에는 수, operators 리스트에는 연산자 2. dfs 탐색으로 계산 결과(result)와 어디까지 계산했는지 인덱스(index)를 넘겨주며 괄호는 치는 경우를 나누어갔다. 3. 괄호는 치는 경우는 다음과 같이 구분했다. 3 + 8 * 7 - 9 * 2 인 경우, 3 + 8 * ..

• format_list_bulleted Algorithm
• · 2023. 7. 22.
• textsms

[BOJ] 17070 파이프 옮기기 1 (Java)

1. 문제 링크 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 2.1. 접근법 (D..

• format_list_bulleted Algorithm
• · 2023. 7. 16.
• textsms

[BOJ] 21609 상어 중학교 (Java)

1. 문제 링크 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 2. 접근법 0. 변수 선언 PriorityQueue groups: 만들 수 있는 블록 그룹을 담아 우선순위에 따라 타겟 블록 그룹을 선정 1. 타겟 블록 그룹 찾기 1.1. searchMaxGroup() 함수를 통해 타겟 블록 그룹 반환하기 1.2. 그룹별 id 값을 매긴 후, 기준 블록을 찾아 bfs() 함수에 넘기기 1.3. bfs를 통해 블록의 수(cnt), 무지개 블록..

• format_list_bulleted Algorithm
• · 2023. 7. 8.
• textsms

[BOJ] 1062 가르침 (Java)

1. 문제 링크 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 2. 접근법 알파벳은 26 글자이므로 2^26으로 선택한 k개의 글자들을 표현할 수 있다. ex) a == 1 b == 10 z == 10000000000000000000000000 a, b, z를 선택했다면 == 10000000000000000000000011 이렇게 선택한 글자들을 비트 마스크로 표현하고, 입력받은 각 단어 또한 글자 중복을 제거하여 비트 마스크로 표현한..

• format_list_bulleted Algorithm
• · 2023. 6. 26.
• textsms

[BOJ] 14442 벽 부수고 이동하기 2 (Java)

1. 문제 링크 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 2. 접근법 일반적인 bfs와 다른 것은 벽을 부술 수 있다는 것 그렇다면 어디를 부쉈는지에 따라 visited 배열이 달라질 것이다. 부술 수 있는 최대 벽의 수 k는 1부터 10까지이므로, visited를 3차원 배열로 선언하여 k에 따른 방문 여부를 저장한다. visited[][][]를 3차원으로 선언한 것 외에는 특별한 점 없음 3. 코드..

• format_list_bulleted Algorithm
• · 2023. 6. 25.
• textsms

[BOJ] 17837 새로운 게임 2 (Java)

1. 문제 링크 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 2. 접근법 1. 변수 선언 - Piece[] pieces: 말들의 정보 저장 - int[][] color: 보드 색상 저장 - ArrayList[][] board: 보드 위 말들의 idx 저장 2. 1번부터 k번 말까지 각 말의 방향에 따라 이동할 위치를 찾고 해당 위치의 color[][] 값에 따라 움직이기 2.1. 이동 시, 말들을 쌓을 때 ArrayList tempPie..

• format_list_bulleted Algorithm
• · 2023. 6. 19.
• textsms

[BOJ] 17779 게리맨더링 2 (Java)

1. 문제 링크 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 2. 접근법 1. 4개의 기준점 구하기 1.1. board의 모든 점을 순회하며 기준점(x, y)을 잡는다. 1.2. 기준점을 기준으로 범위를 넘어가지 않는 d1, d2 값을 설정해 나머지 3개의 기준점을 잡는다. 1.3. 4개의 기준점은 point[][]에 저장 2. 구한 4개의 기준점을 기준으로 경계선 여부를 isBorder[][]에 저장 3. 각 선거구의 인구수 구하기 3.1. ..

• format_list_bulleted Algorithm
• · 2023. 6. 18.
• textsms