전체 글

전체 글

    [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배열을 참고하여 빙산의 높이를 줄인다. 위의 과정을 종..

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

    [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 를 시작할 때 불이 지훈이보다 먼저 시작해야 한다는 것이다. 점..

    [Java] 백준 6198 (옥상 정원 꾸미기) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 6198 (옥상 정원 꾸미기) Gold 5

    Problem : https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net Approach 스택Stack 자료구조를 잘 이용해야 하는 문제이다. 스택을 빌딩의 높이 기준 내림차순 상태를 유지시키도록 구성하는 것이 문제 풀이의 포인트이다. 주요 문제 풀이 로직은 빌딩을 순차적으로 접근함을 전제로 다음과 같다. 스택이 비어있지 않고 스택의 top이 현재 빌딩의 높이 이하면 pop을 진행하며, ans에 (현재 빌딩 idx) - (스택 top의 빌딩 i..

    [Java] 백준 16986 (인싸들의 가위바위보) Gold 3
    Algorithm/Baekjoon Online Judge

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

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

    [Java] 백준 16985 (Maaaaaaaaaze) Gold 3
    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) 로 가는 ..

    [Java] 백준 16957 (체스판 위의 공) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16957 (체스판 위의 공) Gold 4

    Problem : https://www.acmicpc.net/problem/16957 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙 www.acmicpc.net Approach Union-Find 성격의 개념과 DFS를 혼용하여 풀이한 문제이다. 처음엔 모든 위치를 기준으로 DFS를 수행하여 정답을 구하였다. 이 방법은 TLE(Time Limit Error)가 발생한다. 그러므로 다른 방법을 사용해야 한다. 시간초과를 받은 코드와 정답처리를 받은 코드를 함께 게시하겠다. DFS는 불가피하다. 그러므로 DFS의 횟수를 줄이면서 알고..

티스토리툴바