대웅짱님의 블로그
문제: https://www.acmicpc.net/problem/9328 주어진 정보로 상근이가 몇 개의 문서를 훔칠 수 있는지를 묻는 문제이다. 그래프 탐색문제이므로 BFS로 풀면 되지만 문제가 까다롭다. 바로 열쇠를 획득했을 때 이전에 탐색했던 문을 다시 찾아가 열고 또 계속해서 탐색을 진행할 수 있다는 점이었는데 처음에 문제를 풀 때는 너무 일차원적으로 생각해서 그냥 열쇠를 획득하면 빌딩 입구(테두리 중에서 '*'이 아닌 곳)들을 다시 처음부터 탐색을 진행했다. 즉 빌딩 입구들을 벡터에 다 넣어놓고 for문을 돌면서 각 입구마다 bfs를 진행하고 bfs진행중 열쇠를 만나면 그 열쇠지점을 '.'으로 바꾸고 for문을 다시 처음부터 수행하도록 했었는데 이렇게 하니까 시간이 무려 900ms가 넘었다. 예..
문제: https://www.acmicpc.net/problem/4991 로봇 청소기의 시작위치와 로봇 청소기가 치워야 할 쓰레기들의 위치가 주어졌을 때 로봇이 모든 쓰레기들을 치우는데 필요한 최소 움직임을 출력하는 문제이다. BFS를 이용해 로봇 청소기와 각 쓰레기들 간의 거리를 모두 계산 후 next_permutation을 이용해 모든 수열에 대해 값을 더해보고 최솟 값을 출력해 주었다. 사실 next_permutation말고 DP를 이용해도 가능한데 쓰레기의 최대 개수가 10개 밖에 되지 않아서 그냥 완탐으로 구현했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455..
문제: https://www.acmicpc.net/problem/5427 테스트케이스와 현재 빌딩의 너비와 높이, 빌딩 정보가 주어졌을 때 상근이가 불이 번지는 속도보다 출구에 먼저 도달할 수 있냐고 묻는 문제이다. 많은 해결 방안이 있겠지만 나는 출구를 기준으로 BFS를 이용해 최단경로를 구하는 방법으로 풀었다. 먼저 모든 출구(가장자리의 . )들을 큐에 넣어놓고 각각 출구마다 BFS를 수행한다. BFS 수행 중 가장 먼저 만나는 특이점, 즉 벽(#)과 길(.)을 제외하고 불(*)과 상근이(@)중 어떤게 더 가까운지만 확인해서 상근이가 불보다 가까운 출구가 있다면 그곳으로 나갈 수 있다는 뜻이므로 출구부터 상근이까지의 길이를 계산해 반환하고 모든 출구에대해 수행한 후 최솟 값을 찾는 방법으로 풀었다. ..
문제: https://www.acmicpc.net/problem/2146 여러 개의 섬들을 잇는 다리중 가장 짧은 다리의 길이를 구하는 문제이다. 결국 문제를 해석하면 여러개의 컴포넌트가 주어지고 이 컴포넌트 사이의 가장 짧은 길이를 찾는 문제이다. 먼저 컴포넌트끼리의 구분을 지어야하기 때문에 DFS로 각 컴포넌트에 숫자를 부여했다. 그 후 최단 경로를 모든 섬 정점에서 BFS를 이용해 구하고 그 중 최솟값을 출력했다. BFS를 수행할 때 각 섬들에게 번호를 부여하고 바다를 0 으로하여 만약 현재 정점의 섬 번호와 다른 섬 번호를 발견하면 거기서 BFS 종료를 시켜 현재 정점에서의 가장 가까운 섬까지의 거리를 계산하였다. 육지에서의 이동은 불 필요하므로 현재 보고있는 정점이 내 섬 번호와 같다면 더이상 ..
문제: https://www.acmicpc.net/problem/5014 빌딩의 높이 F, 스타트링크의 층 G, 현재 층 S, 위로 U층, 아래로 D층이 인풋으로 주어졌을 때 현재 층에서 목표 층 까지 최소 몇 번의 U 또는 D 버튼을 눌러야 하는지를 묻는 문제이다. 만약 U나 D를 눌렀을 때 갈 수 없는 층이면 가지 않는다. Ex) F = 78, S = 50, U = 30 일 때 현재 층에서 U버튼을 누루면 80층이지만 80층은 존재하지 않는 층이기 때문에 가지 못한다. 현재 층에서 위 또는 아래 버튼을 한 번씩 눌러보고 갈 수있으면 큐에 넣어 계속해서 확인해주는 방법으로 풀었다. 즉 거리 값이 모두 1일 경우의 최단거리를 구하는 문제이므로 BFS를 이용했다. 만약 큐가 빌 때 까지 목표층에 도달하지 ..
문제: https://www.acmicpc.net/problem/9518 R*S의 배열이 주어진다. 배열은 이미 좌석 주인이 있으면 o 빈자리이면 . 로 정보로 준다. 상근이가 가장 마지막에 자리에 앉을 때 (빈자리 중에서 한자리) 사람들이 가장 많은 악수를 할 수 있는 횟수를 구하는 문제이다. 문제 해결 방안은 상근이를 빈자리에 한 번씩 앉혀본 후 8방향을 확인해봐서 o인 좌석의 개수를 세면 된다. 다만 문제에 함정이 몇 가지 있다. 첫째로 상근이의 악수 횟수를 구하는 문제가 아니라 모든 사람의 악수 횟수를 구하는 문제이다. 둘째로 빈자리가 없는 예도 있다. 첫 번째 함정은 간단하다. 그냥 악수 횟수를 상근이의 악수 횟수만 구하는게 아니라 모든 사람의 악수 횟수를 구한 뒤 마지막 결과 값에 나누기 2 ..
문제: https://www.acmicpc.net/problem/9997 N개의 단어가 주어졌을 때 이 단어들의 조합으로 a-z까지의 알파벳을 한 번씩 사용하는 문장을 몇 개 만들 수 있는지를 묻는 문제이다. 단어들은 한 번씩만 사용할 수 있다. 예) abcd efgh ijkl mnop qrst uvwxyz 라는 단어들이 주어졌을 때 이 단어들을 모두 한 번씩 사용하면 a-z까지의 알파벳을 모두 한 번씩 사용하게 되므로 상근이가 만들 수 있는 테스트 문장의 개수는 1개이다. 나는 비트 마스크를 이용하여 풀었다. 먼저 시프트 연산을 통해 각 단어의 값을 저장한다. 각 알파벳의 값이 비트의 한 자리씩 담당하게 된다. 예를 들어 단어가 'abc'이고 단어를 저장하는 변수가 str, 단어의 값을 저장할 변수가 ..
문제: https://www.acmicpc.net/problem/2823 행과 열, 빌딩과 길이 주어졌을 때 유턴을 하지 않고 모든 길을 지나면서 다시 시작 위치로 올수 있는지를 물어보는 문제이다. 간단하게 DFS를 이용해서 풀었다. DFS로 갈수 있는 길을 모두 확인하면서 만약 현재 길에서 세 방면 이상이 막혀(빌딩이나 지도의 끝)있다면 이 길은 막다른 길이라고 판단 할 수 있다. 길은 모두 이어져 있다고 문제에 명시되어 있으므로 DFS는 한 번만 수행하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include#includeusing namespace std;int n, m..