BFS

    [java] 백준 7576 (토마토1) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 7576 (토마토1) Silver 1

    Problem : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net Approach 시작점이 여러개인 최단경로 문제이다. 문제에서 배열의 요소가 1인 모든 곳이 시작점이다. (따라서 요소가 1인 모든 좌표를 큐에 넣고 BFS를 수행한다.) 벽이 -1 로 막혀있지 않고, 범위를 벗어나지 않으며, 방문하지 않았다면, 방문하면서 직전 위치의 값 + 1을 방문하는 곳에 저장한다. BFS가 완전히 모두 수행된 후, 최단경로 배열을 검사하여..

    [java] 백준 2178 (미로 탐색) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2178 (미로 탐색) Silver 1

    Problem : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net Approach (1, 1)에서 (n, n)까지의 최소 이동거리를 구하는 문제이다. BFS를 사용하여, 범위를 벗어나지 않고, 요소가 1이며, 방문하지 않았다면, 큐에 집어넣는 식으로 진행하였다. 방문할 곳에 직전 곳에 있는 값+1 을 저장해주면 (n, n)에 최소 비용이 저장될 것이다. BFS를 구현만 할줄 안다면, 쉬운 문제가 될 것이다. Code import java.io.*; import java.uti..

    [java] 백준 2667 (단지번호붙이기) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2667 (단지번호붙이기) Silver 1

    Problem : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net Approach 보통 지도 형식의 배열이 나오면 BFS로 푸는게 더 나은 것 같다...(필자 생각) BFS, DFS 모두 풀이가 가능해도 더 좋은 풀이가 있는 문제처럼, 지도를 통한 탐색의 경우 필자는 BFS를 더 선호한다. (더 간단하기 때문 ㅎㅎ) 이 문제는 감을 익히기 위해서 두 방법 모두로 풀어봤다. 또한 이 문제는 프로그래머스에도 유사한 문제가 있다. 밑의 링크는 그 문제..

    [java] 백준 1260 (DFS와 BFS) Silver 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 1260 (DFS와 BFS) Silver 2

    Problem : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net Approach BFS(Breadth-First Search), DFS(Depth-First Search) 의 기본 문제이다. 일단 BFS, DFS 가 어떤 방식으로 돌아가는지를 알아야 한다. 사전적 정의는 DFS는 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다는 방식이고..

    [java] 프로그래머스 (카카오프렌즈 컬러링) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (카카오프렌즈 컬러링) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr Approach 2017 카카오코드 예선문제로, 간단한 BFS 문제이다. 일단 모든 점을 검사한다. 검사하면서 방문할 수 있으면 방문하면서 최대 영역의 넓이와 영역의 개수를 갱신하고 방문표시를 한다. Code import java.util.LinkedList; import java.util.Queue; public class KakaoFriends..

    [java] 백준 13913 (숨바꼭질 4) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 13913 (숨바꼭질 4) Gold 4

    문제 원문 링크 : https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Approach 대표적인 BFS문제로, 최단시간을 이루는 경로 또한 구해야 하는 문제이다. 현재 위치가 X 일 때, 1초 후에 X - 1 또는 X + 1 또는 2 * X 위치로 갈 수 있다. 처음 큐에 N을 넣은 후 하나씩 뺀다. 뺀 수에 +1, -1, *2를 하여 범위(0 ~ 100,000)를 넘지 않는다면 큐에 넣는다. ..

    [java] 백준 13549 (숨바꼭질 3) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 13549 (숨바꼭질 3) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Approach 대표적인 BFS문제로 백준 1679번 숨바꼭질 문제와 단 한개의 조건을 제외하고 똑같은 문제이다. 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의..

    [java] 백준 12851 (숨바꼭질 2) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 12851 (숨바꼭질 2) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net Approach 대표적인 BFS 문제로, N to K의 최단시간과 최단시간으로 가는 방법을 구하는 문제이다. 현재 위치가 X 일 때, 1초 후에 X - 1 또는 X + 1 또는 2 * X 위치로 갈 수 있다. 처음 큐에 N을 넣은 후 하나씩 뺀다. 뺀 수에 +1, -1, *2를 하여 범위(0 ~ 100,000)를 넘지 않..

    [java] 백준 1697 (숨바꼭질) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1697 (숨바꼭질) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Approach 대표적인 BFS 문제로 Queue와 visited[] 배열을 이용하여 풀이를 생각했다. 현재 위치가 X 일 때, 1초 후에 X - 1 또는 X + 1 또는 2 * X 위치로 갈 수 있다. 처음 큐에 N을 넣은 후 하나씩 뺀다. 뺀 수에 +1, -1, *2를 하여 범위(0 ~ 100,000)를 넘지 않는다면 큐에 넣는..

    [java] 백준 2533 (사회망 서비스(SNS)) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 2533 (사회망 서비스(SNS)) Gold 3

    문제 원문 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net Approach (Wrong) 내가 처음 생각했던 잘못된 접근법 처음에는 아무 노드나 루트로 잡고 level을 매겨서 min(홀수레벨 총 노드개수, 짝수레벨 총 노드개수)로 구현하면 될 줄 알았다. 질문 게시판에 있는 대부분의 반례 또한 통과되어 맞는 풀이법이라고 생각했으나, 다음과 같은 반례가 있었다. Approach (Correct) 자신이 얼리어답터인지, 아닌지 일때..

티스토리툴바