백준
백준 2110번 : 공유기 설치
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 우아한 테크코스 코딩테스트를 준비할겸 기초 알고리즘을 복습하기 위해 접했던 이분 탐색 문제다. 기존에 풀었던 이분 탐색 문제와 달리 바로 해결 아이디어가 떠오르지 않아서 질문 게시판을 참고해서 해결했다. 일직선(1차원) 좌표상의 특정 좌표에 집이 존재하고 주어진 개수만큼의 공유기를 집에 설치하고자 한다. 공유기는 한 집에 1개만 설치가능하며 주어..
백준 17836번 : 공주님을 구해라!
https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 용사는 마왕성에서 공주를 구해야한다. 마왕성은 1x1 크기의 정사각형으로 이뤄져있고, 각 칸은 이동할 수 있는 길 또는 벽이다. 용사는 인접 칸으로 이동하기 위해서 1시간이 걸리고 주어진 시간 내에 공주에게 도달해야한다. 마왕성 어딘가에는 용사의 무기 "그람"이 1개 존재하는데, 이 그람을 가지면 그 순간부터 벽을 부수고 지나갈 수 있다. 용사가 공주를 구할 수 있는지 여부를 확인..
백준 13549번 : 숨바꼭질 3
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제의 첫 인상은 그래프 탐색 문제처럼 보이지 않고 독특했다. 0부터 100,000까지 점이 존재하고 수빈이와 동생이 이 점들 중 한 곳에 존재한다. 수빈이는 현재 위치를 기준으로 1만큼 뒤로 가거나 앞으로 갈 수 있지만 시간이 1초 소모된다. 또한 수빈이는 시간 소요없이 현재 위치에 2배가 되는 곳으로 순간이동 할 수 있다. 수빈이가 동생을 찾기 위해 소요되..
백준 2636번 : 치즈
https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 고민하다가 자체적으로 난이도를 높혀버린 문제이다. 문제 풀이 자체는 다른 그래프 알고리즘과 크게 다르지 않다. 문제를 간단히 요약하자면, 1x1 크기의 정사각형으로 이루어진 판 위에 치즈가 일부분 올려져있고 이 치즈는 공기에 노출된 상태에서 1시간이 지나면 녹아 없어진다. 치즈엔 구멍이 뚫려 있는데 다행히도 이 구멍엔 공기가 없어서 치즈 안쪽에서부터 녹아 없어지진 않지만, 바깥 공기가 구멍 안쪽으로 들어갈..
백준 16234번 : 인구 이동
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 유독 풀면서 실수가 많았던 문제. 풀이 자체는 다른 BFS 그래프 탐색 문제와 다르지 않다. 크기가 NxN인 땅 안에 1x1 크기의 나라가 하나씩 존재한다. 각 나라별로 인구수가 정해져있고 인접 나라와의 인구수의 차이에 따라 인접한 국경선을 열 수 있다. 그렇게 해서 열린 국경선을 따라 하루동안 인구가 이동하는데 특정 나라에서 출발하여 방문이 가능한 나라들은 모두 연합이며, 한 연합..
백준 16956번 : 늑대와 양
https://www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net DFS, BFS를 이용한 그래프탐색 카테고리에 포함된 문제들을 풀다가 특이한 문제를 발견했다. 문제를 요약하면 1x1 크기의 칸으로 나뉘어진 목장의 상태를 보고, 자유롭게 움직일 수 있는 늑대가 양에게 접근할 수 없게 울타리를 친다. 문제를 보고 이해했을땐 단순히 처음 주어진 늑대의 위치 좌표를 초기 큐에 넣고 BFS 탐색을 하면서 인접한 칸들을 확인하며 인접칸에 양이 있다면 그 자리에 울타리..