[Java] 백준 4179 (불!) Gold 4

Problem : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net Approach BFS를 이욯하는 문제이다. 먼저, 입력을 받으면서 # 과 F인 부분은 visited배열에 true를 표시한다. 어차피 지훈이가 방문할 수 없는 곳이기 때문이다. 또한 지훈이가 방문한 곳을 불이 방문할 필요도 없다. 불보다 지훈이가 먼저 도착한 것이 되기 때문이다. 주의할 점은, BFS 를 시작할 때 불이 지훈이보다 먼저 시작해야 한다는 것이다. 점..

→2021.06.28

Algorithm/Baekjoon Online Judge

[Java] 백준 16986 (인싸들의 가위바위보) Gold 3

Problem : https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net Approach 순열을 이용한 완전탐색과 구현이 필요한 문제였다. 먼저 문제에서 주의할 점을 짚고 가자. 입력으로 주어지는 경희와 민호의 패는 라운드 별 패가 아니다. 경희와 민호가 참여하는 게임에서 내는 패의 순서일 뿐이다. 지우가 질 경우에도 사용한 적이 없는 패를 내야한다. (서로 다른 패로 이기는 경우만을 찾는 것이 아니다.) 문제 풀이의 주요 로직은 다음과 같다..

→2021.06.24

Algorithm/Baekjoon Online Judge

[Java] 백준 16985 (Maaaaaaaaaze) Gold 3

Problem : https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net Approach BruteForce(완전탐색) 순열 + BFS + 구현 개념이 사용된 문제였다. 문제 풀이에 사용된 주요 로직은 다음과 같다. 주어진 판들의 순서를 순열로 구하여 쌓는다. 쌓인 판들을 0도, 90도, 180도, 270도를 돌려서 나오는 모든 경우를 찾는다. 2번 과정에서 찾아진 각 경우에 대해 (0, 0, 0) ~ (4, 4, 4) 로 가는 ..

→2021.06.21

Algorithm/Baekjoon Online Judge

[Java] 백준 16988 (Baaaaaaaaaduk2 (Easy)) Gold 3

Problem : https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net Approach BruteForce 완전탐색과 BFS의 개념을 같이 사용한 문제였다. 일단 문제 풀이의 주요 로직은 다음과 같다. 먼저 BFS를 이용하여 상대편 돌을 Grouping한다. 그리고 그룹핑한 결과를 groups에 저장한다. 그리고 Backtracking을 사용하여 돌을 2개 놓는 모든 경우를 만든다. 그 상태에서 상대 돌을 ..

→2021.06.15

Algorithm/Baekjoon Online Judge

[Java] 백준 1981 (배열에서 이동) Gold 1

Problem : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net Approach 이분탐색 + BFS 문제이다. 꽤 어렵게 문제를 풀었다. 문제 풀이에 앞서, 입력을 받으면서 구해놔야 할 것이 있다. 배열의 값중 최솟값 minNum과 최댓값 maxNum을 이분탐색의 left와 right에 이용하기 때문이다. left는 0이다. (배열의 값이 모두 같은 경우 최대 - 최소 = 0이다.) right는 maxNum - minN..

→2021.06.09

Algorithm/Baekjoon Online Judge

[Java] 백준 1939 (중량제한) Gold 4

Problem : https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net Approach 이분탐색과 DFS/BFS를 사용하는 문제이다. 먼저 입력을 받으면서 그래프를 구성한다. 와중에 중량제한의 최솟값과 최댓값 또한 같이 구한다. 이 두 값이 이분탐색에 쓰일 left와 right가 될 것이다. 이 중량제한 값을 이용하여 BFS를 수행한다. 시작 섬을 출발하여 도착 섬에 도달할 수 있다면, ans를 갱신하..

→2021.06.04

Algorithm/Baekjoon Online Judge

[Java] 백준 16933 (벽 부수고 이동하기 3) Gold 1

Problem : https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net Approach BFS문제이다. 백준 14442 (벽 부수고 이동하기 2) 문제에 조건이 하나 더 달린 문제이다. 여기서의 visited배열은 4차원 배열이다. visited[n][m][k][a] 는 (n, m) 위치를 k번 벽을 부신 채로 낮(a = 0) 혹은 밤(a = 1)에 방문했다는 뜻이다. 문제 풀이의 주요 로직은 다음과 같다. 낮이라..

→2021.05.16

Algorithm/Baekjoon Online Judge

[Java] 백준 14442 (벽 부수고 이동하기 2) Gold 3

Problem : 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 Approach 대표적인 BFS문제이다. 일단 visited[i][j][k] 는 (i, j) 위치에 k번 벽을 부순 채로 도달했는지를 나타내는 배열이다. 문제를 푸는 주요 BFS 로직은 다음과 같다. 현재 위치에서 상하좌우 방향으로 벽이 아니라면 cnt++ 한 후, 이동한다. (이 때 visited 배열에 벽을 부순 횟수는 증가시키지 않고 표시..

→2021.05.16

Algorithm/Baekjoon Online Judge

[Java] 백준 16954 (움직이는 미로 탈출) Gold 4

Problem : https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net Approach 이동 가능한 곳이 동적으로 변하는 환경에서의 BFS문제이다. 변하는 방법은 위에서 아래로 한 칸씩 내려오는 방식이다. 문제를 푸는 로직은 다음과 같다. 현재 위치가 벽이 아니라면, 현재 위치 포함, 상하좌우 대각선4방향으로 이동한다. 벽을 위에서 아래 방향으로 한 칸씩 내린다. 무한 루프를 방지하기 위해 방문 여부를 나타내는 flag 변수를 하나 둔다...

→2021.05.15

Algorithm/Baekjoon Online Judge

[Java] 백준 3055 (탈출) Gold 5

Problem : https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net Approach 이동 가능한 곳이 동적으로 변하는 환경에서의 BFS문제이다. 문제를 푸는 주요 로직은 다음과 같다. 다음에 물이 찰 예정인 곳은 비버가 방문할 수 없으니 물을 먼저 전파시키고 비버를 이동시킨다. 물을 전파시킨다. 비버를 이동할 수 있는(물이 차지 않은) 곳들을 방문한다. 즉, 비버따로 물따로 각각 BFS가 수행되어야 한다. (ps. cnt 배열을 사용하지 않고 Point 클래..

→2021.05.15

티스토리툴바