BFS

    [Java] 백준 14502 (연구소) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 14502 (연구소) Gold 5

    Problem : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net Approach 완전탐색(BruteForce)과 BFS를 함께 사용하는 문제이다. 문제 풀이 주요 로직은 다음과 같다. 0인 곳들 중 3군데를 골라서 벽을 세운다. 벽을 3개 세웠으면 그 상태에서 BFS를 수행하여 바이러스를 전파시킨다. 전파 시킨 뒤에 0의 개수를 찾는다. 모든 경우를 다 탐색하여, 안전한 구역의 최대 개수를 구한다. Code import java.io.*; import j..

    [Java] 백준 6087 (레이저 통신) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 6087 (레이저 통신) Gold 4

    Problem : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net Approach BFS + DP 문제라고 볼 수 있다. 특정 위치 (x, y)를 방문하는 방법은 여러 방법이 있는데, 그 중 방향 전환을 최소로 하는 방문을 찾는 문제이다. 문제에서 거울이라는 개념이 나오는데, 쉽게 말하여 방향이 변하는 곳엔 거울을 놓을 수 밖에 없다. 따라서, 목표 위치 (x, y)를 방문하는 방법 중, 방향 전환이 최소인 방문을 찾으면 된다. cha..

    [Java] 백준 1963 (소수 경로) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1963 (소수 경로) Gold 4

    Problem : https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net Approach 소수를 찾는 알고리즘과 BFS 개념으로 풀 수 있는 문제이다. 문제 풀이의 주요 로직은 다음과 같다. 먼저 간단하게 에라토스테네스의 체 개념을 이용하여 1 ~ 9999 사이의 숫자들 중 소수를 판별한다. 그리고 난 뒤 현재 숫자에서 숫자 하나만 변경하며 BFS를 수행한다. 숫자를 하나씩 바꾸는 부분을 구현하는게 꽤 까다로울 수 있다. String을 사용할까도 생각해봤지만,..

    [Java] 백준 14395 (4연산) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 14395 (4연산) Gold 5

    Problem : https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net Approach BFS문제이다. 하지만 배열을 사용하여 풀이한다면, 메모리초과를 만날 것이다. Set 에 방문한 곳들만 추가하여, 메모리를 절약하여야 한다. 이것이 가능한 이유는 1 ~ t범위 안에 실제로 방문할 수 있는 숫자는 전체 숫자 대비 몇개 안되기 때문이다. 문제 풀이에 앞서 입력에 따라 간단히 처리할 수 있는 부분과, 필요한 로직을 단순화 시켜보자. s == t..

    [Java] 백준 16940 (BFS 스페셜 저지) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16940 (BFS 스페셜 저지) Gold 4

    Problem : https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net Approach 그래프 정보와 BFS 방문 순서가 주어졌을 때, 주어진 방문 순서가 유효한지를 판단하는 문제이다. 현재 노드 기준으로, 방문하지 않은 인접한 노드들을 모두 set에 넣는다. 그리고 다음 방문 순서가 올바른 BFS 순서인지를 판단한다. 주어진 방문 순서의 끝까지 검사하며, 다음 방문 순서가 set에 없다면 올바르지 않은 방문 순서인 것이다. 주의할 점은, 주어진 방문 순서가 1부터 시작하는지를 검사하여 예외처리를 해주어야 한다. (시작점이 1이라고 가정하고 문제를 푸는데, 주어진 ..

    [Java] 백준 2146 (다리 만들기) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2146 (다리 만들기) Gold 3

    Problem : https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net Approach BFS를 사용하여 풀이할 수 있는 문제이다. 여기서는 섬 인덱싱을 위한 BFS, 그리고 각 섬에서 수행되는 BFS 이렇게 두 가지의 BFS를 사용한다. 문제에서 요구하는 것은, 어떤 섬이든 길이가 최소가 되는 다리 하나를 놓는 것이다. 문제 풀이의 주요 순서는 다음과 같다. 섬 인덱싱을 수행한다. (BFS) 각각의 섬에서 가장 가까운 섬과의 거리를 구한다. (BFS) ..

    [Java] 벡준 16947 (서울 지하철 2호선) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 16947 (서울 지하철 2호선) Gold 3

    Problem : https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net Approach 그래프 정보가 주어졌을 때, 사이클을 구하고, 그 사이클로부터 얼마나 멀리 떨어져 있는지를 구하는 문제였다. 먼저 주의할 점은, 노드의 개수가 N개이고, 간선의 개수도 N개이므로, 사이클(순환선)은 무조건 1개 존재한다는 것이다. 문제 풀이의 순서는 다음과 같다. 먼저 사이클 찾은 뒤, 사이클에 속하는 노드들을 표시한다. (cycle 배..

    [Java] 백준 16946 (벽 부수고 이동하기 4) Gold 2
    Algorithm/Baekjoon Online Judge

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

    Problem : https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net Approach BFS/DFS 문제이다. 하지만 각 점마다 탐색을 한다면 TLE 를 면치 못할 것이다. 각 벽에서 도달할 수 있는 칸이 몇개인지 판단하기 전에 한번의 탐색이 선행되어야 한다. 바로 각 칸이 속하는 그룹의 종류와 그 그룹의 크기를 구해놔야 한다. 따라서 나는 다음과 같은 변수를 사용했다. int[][] group: (i, j) 점이 무슨 그룹인..

    [Java] 백준 1600 (말이 되고픈 원숭이) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1600 (말이 되고픈 원숭이) Gold 5

    Problem : https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net Approach BFS 문제이다. 일반적인 BFS 에 이동할 수 있는 추가적인 방향과 이 추가적인 방향을 사용하는데에 있어 제한을 두는 약간의 제약이 추가되었다. 문제에서 언급하는 말 이동은 횟수제한이 있으므로, 해당 지점에 말 이동을 몇 번 사용하여 최소 이동으로 도착하였는지를 저장하여야 한다. (이 때문에 visited 배열을 3차원으로 선언하였다.) 그 이외..

    [Java] 백준 1261 (알고스팟) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1261 (알고스팟) Gold 4

    Problem : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net Approach 이 문제의 기본 접근법은 갈 수 있는 곳 중 벽이 아닌 곳이 있으면 우선 그 쪽으로 가고, 갈 수 있는 곳이 벽인 곳밖에 없다면 벽을 뚫는다.이다. 이를 구현하는 데에는 여러 방법이 있겠지만, 나는 Deque+BFS, PriorityQueue+BFS 두 가지 방법으로 풀이를 해봤다. 두 방법 모두 풀이가 가능하다. 주의할 점은, 큐에 동일한 ..

티스토리툴바