BOJ

    [Java] 백준 정규표현식(Regular Expression) 문제 모음 및 풀이
    Algorithm/Baekjoon Online Judge

    [Java] 백준 정규표현식(Regular Expression) 문제 모음 및 풀이

    Problem 15881: Pen Pineapple Apple Pen (Bronze 2) code: https://github.com/PaengE/AlgorithmPractice/blob/master/BaekJoon_java/src/BOJ15881.java Problem 10173: 니모를 찾아서 (Bronze 2) 10173번: 니모를 찾아서 여러 문장이 각 줄로 입력되며, 입력의 마지막에는 "EOI" 입력된다. 한 줄은 최대 80개의 글자로 이루어져 있다. www.acmicpc.net code: https://github.com/PaengE/AlgorithmPractice/blob/master/BaekJoon_java/src/BOJ10173.java Problem 1264: 모음의 개수 (Bronze..

    [Java] 백준 18809 (Gaaaaaaaaaarden) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 18809 (Gaaaaaaaaaarden) Gold 2

    Problem : https://www.acmicpc.net/problem/18809 Approach 조합을 이용한 BruteForce 와 BFS + 구현 이 필요한 문제이다. 천천히 생각하고 필요한 부분을 캡슐화하여 메소드를 작성하면 된다. 코드에 사용된 변수 설명은 다음과 같다. availableLands: 배양액을 뿌릴 수 있는 Land를 저장한 리스트 selectedAvailableLands: availableLands에서 g + r개의 Land 를 뽑는 조합에 이용할 boolean 배열 selectedLands: 배양액을 뿌릴 곳으로 선택된 g + r 크기의 배열 selectedGreen: selectedLands 중 초록색 배양액을 뿌릴 곳으로 선택한 boolean 배열 time: 해당 영역에..

    [Java] 백준 3197 (백조의 호수) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 3197 (백조의 호수) Gold 1

    Problem : https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net Approach BinarySearch 를 이용한 BFS + 구현 문제였다. 먼저, 얼음이 며칠 뒤에 녹는지에 대한 전처리가 필요하다. (코드에서는 iceberg라고 표현했다.) 얼음에 대한 전처리는 다음 과정으로 처리하였다. findIcebergNearWater(): 물과 인접한 얼음들을 구하였다. icebergsNearWater 큐 : 이 변수는 ..

    [Java] 백준 17071 (숨바꼭질 5) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17071 (숨바꼭질 5) Gold 1

    Problem : https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net Approach 숨바꼭질 시리즈에서 동생이 움직인 버전 이다. 일반적인 BFS로는 시간초과(TLE)가 발생한다. 규칙을 찾아 시간을 단축시켜야 한다. 처음엔 일반적인 BFS를 하여 시간초과를 받았다. 시간초과 코드 또한 아래에 기록했다. 규칙은 다음과 같다. 수빈이가 A초에 X지점을 도착했다고 한다면, A+2초에도 X지점을 도착할 수 있다. ..

    [Java] 백준 16920 (확장 게임) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16920 (확장 게임) Gold 2

    Problem : https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net Approach BFS + 구현이 필요한 문제이다. 먼저 사용된 변수 설명을 하겠다. starts[i] : 플레이어 i 의 BFS 시작점들. s[i] : 플레이어 i 가 한번에 이동할 수 있는 거리. visited[i][j] : (i, j) 위치를 방문했는지를 표시. cnt[i] : 플레이어 i 의 땅 개수. 위 변수들을 사용한 문제 풀이 주요 로직은 다음과 같다. 플레이어의 ..

    [Java] 백준 11967 (불켜기) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 11967 (불켜기) Gold 3

    Problem : 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 Approach 일반적인 BFS가 아닌 재귀와 BFS를 혼용하여야 했던 문제이다. 문제 풀이의 주요 로직은 다음과 같다. (0, 0)을 시작점으로 BFS를 진행하면서, 가능한 스위치들을 모두 켠다. 해당 BFS에서 새 스위치를 켰다면, (0, 0)을 시작점으로 다시 BFS를 진행한다. (새로운 스위치를 올린 여부를 flag에 ..

    [Java] 백준 6593 (상범 빌딩) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 6593 (상범 빌딩) Gold 5

    Problem : https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net Approach 일반적인 2차원 배열이 아닌 3차원 배열에서의 BFS 문제이다. 2차원 배열이나 3차원 배열이나 BFS는 비슷하게 구현된다. 움직일 수 있는 방향이 상하좌우 4방향에서 다른 층으로 넘어가는 2방향이 추가되어 총 6방향을 고려해주는 차이밖에 없다. 주의할 점으로는 시작점과 도착점이 임의로 주어지므로 따로 저장한 뒤에 활용하여야 한다. (항상 시작점이 (0,0,0), 도착..

    [Java] 백준 5014 (스타트링크) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 5014 (스타트링크) Gold 5

    Problem : https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net Approach 간단한 BFS 문제이다. 빌딩의 최고층이 F인데, F층보다 큰 층에서 내려오는 부분과 1층보다 낮은 층에서 올라오는 부분을 제외해주면 되기에 배열의 크기를 정하기 용이하다. 기본적인 BFS문제로, 풀이하기에 어렵지 않다. Code import java.io.*; import java.util.ArrayDeque; import java.util.Arrays; import jav..

    [Java] 백준 5427 (불) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 5427 (불) Gold 4

    Problem : https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net Approach BFS 문제이다. 나는 사람이 지나간 곳과 불이 지나간 곳을 따로 체크하여 구성하였다. 하지만 문제를 풀고나서 생각해보니 불이 사람보다 먼저 움직이게 한다면 같은 visited 배열을 사용해도 될 것 같다. (사람이 먼저 방문하면 불이 나중에라도 그 곳을 방문할 필요가 없기 때문이다. 사람보다 더 늦게 방문) 문제 풀이의 주요 로직은 다음과 같이 간단하다. 일반적인 BFS 를..

    [Java] 백준 2573 (빙산) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2573 (빙산) Gold 4

    Problem : https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net Approach BFS를 이용한 구현이 필요한 문제였다. 나의 문제 풀이 주요 로직은 다음과 같다. 빙산을 Grouping 하여 빙산 그룹의 개수를 찾는다. 이 때, 빙산 그룹의 개수가 0이거나 2이상 이면 그만둔다. 모든 지점 (x, y)에 대하여 바다와 얼마나 접하는지를 oceanCnt배열에 저장한다. oceanCnt배열을 참고하여 빙산의 높이를 줄인다. 위의 과정을 종..

티스토리툴바