목록알고리즘 (30)
대웅짱님의 블로그
문제: https://www.acmicpc.net/problem/12100 2048 이라는 게임이 있다. 난 이 게임을 핸드폰 앱으로 처음 했었는데 상 하 좌 우 움직이면서 같은 숫자들을 합치면서 높은 수를 만들어 내는 게임이다. 이 문제 이름은 2048 (Easy) 이다. 주어진 정보를 이용해 2048 게임을 시뮬레이션 해보는 문제이다. Easy라는 단어가 들어간 이유는 아마 5번의 횟수제한 때문인 것같다. 친절하게 5번의 횟수를 정해준 이유는 완전탐색을 하라는 뜻으로 받아들이면 된다. 마침 보드의 최대도 20*20 밖에 안된다. 상 하 좌 우를 나타낼 1~4까지의 숫자를 5자리 순열로 만들고 (ex: 11111 11112 11113 .... 44443 44444) 각 순열의 이동이 모두 끝난 후의 보..
문제: https://www.acmicpc.net/problem/13460 오랜만에 구슬 탈출 문제를 풀어봤다. 몇 가지를 제외하고는 일반 bfs문제와 크게 다르지 않다. 1. 가져가는 주체가 빨간 구슬과 파란 구슬 두 개이다. 2. 한 번에 한 칸씩 움직이는 것이 아니라 갈 수 있는 곳 까지 움직인다. 3. 빨간 구슬만 목적지에 도착해야 한다. 이 것만 신경써주면 크게 어렵지 않은 문제이다. 다만 생각할게 많아서 귀찮을 뿐. 문제 푸는 원리는 이렇다. 큐에 빨간 구슬과 파란 구슬의 좌표를 가지고 간다. 무한 루프 방지를 위해 visit 배열을 사용하는데 여기도 마찬가지로 빨간 구슬과 파란 구슬의 좌표를 한번에 가진다. 그리고 각각 구슬을 서로 신경쓰지 않고 같은 방향으로 굴릴 수 있는 곳 까지 굴린다...
문제: 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 ..