live the life you love

www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 첫 플레문제였다. 단순히 다익스트라나 BFS로 하면 될 것 같았는데 아무리 고민을 해도 시간복잡도를 알맞게 할 수 없을 것 같아서 다른 블로그를 보고 풀었다. 찾아보니 이런 유형의 문제는 0-1 BFS라고 한다. 가중치가 0과 1만 있는 그래프에서 사용할 수 있는데, 기존의 BFS는 방향탐색을 마치고, 다음에 갈 지점을 큐에 삽입할 때 단순히 큐의 맨뒤에 push 했다. 또한, 다익스트라의 경우도 우선순위 큐를 사용하여 항..

www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 맨 처음에는 단순히 전체 배열을 탐색하는 BFS 코드를 짰더니 시간 초과가 발생했다. 최악의 경우 O(N^3) 까지 들어 올 수 있기 때문에 그렇다. 그래서 조금 다른 방법을 사용했다. 비어있는 부분의 위치를 모두 큐에 삽입하고, 이를 기준으로 BFS 탐색을 한다. 8방 탐색을 하는 동안 모래성을 만나면 해당 모래성에서 1을 빼주고, 큐에서 popleft를 한다. 만약 모래성의 값이..

www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기본적인 BFS에 방문했던 경로를 따로 저장하여 경로를 역순으로 탐색하는게 추가된 문제였다. 수빈이가 갈 수 있는 3가지 경로을 모두 큐에 같이 저장하고 해당 경로마다 탐색을하면 분명 시간초과 또는 메모리 초과가 발생할 것이다. 기본적으로 수빈이가 이미 갔던 경로는 파악하기 위해서는 bool 타입의 visited 배열로 단순히 방문체크만 해주는 것에 한가지를 더 추가해야한다. ..

www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 카테고리 분류에 BFS가 있어서 당황했던 문제이다. 이런류의 문제를 BFS에 접목시킨다는 발상을 하기가 어렵다. 실제 코테에 나왔다면 못풀었을 것이다. 어려웠고 놓쳤던 부분은 다음과 같다. '123' 을 R 연산하면 312가 아니라, '2031'이된다. 숫자는 무조건 4자리로 고정되어있기 때문이다. 숫자 하나당 4가지의 경우의 수가 발생해서 4^n 만큼의 경우의 수가 나올 거 같은데, 어떻게 시간 ..

www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제의 구현 로직은 다음과 같다. 모든 치즈가 다 녹았는지 확인한다. 남은 치즈가 있다면 전부 녹을 때 까지 아래의 과정을 반복한다. 다른 치즈 내부 공간에 있지 않은 치즈들 중 외부 공기와 2개 변 이상 접촉한 치즈를 체크한다. 체크된 치즈를 녹인다. 1, 3번은 크게 어렵지 않은데 2번이 조금 까다로운 편이었다. 단순히 상,하,좌,우 중 공기인 칸이 2개 이상인지만 확인하면 안된다. 왜냐하면 상하좌..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 전형적인 BFS 탐색을 활용해서 푸는 문제였다. 상근이는 무조건 집 -> 편의점 -> 편의점 .. -> 페스티벌 로 움직이기 때문에 다음번 편의점에 가서 항상 맥주를 최대로 살 수 있다. 굳이, 이동할 때 마다 이동거리를 50m로 나누면서 이동 가능 여부를 판단하지 않고 맥주를 20개 먹었을 때 갈 수 있는 최대 거리인 1,000m를 기준으로 다음번 편의점 또는 페스티벌 장 까지의 거리가 1..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다. www.acmicpc.net 이차원 벡터를 만들고, 전형적인 bfs 탐색을 하는 문제였다. 시작지점과 연결되어있는 모든 정점을 방문하며, 기존에 방문하지 않은..