문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 방법 벽을 부쉈을 때 이동할 수 있는 칸의 갯수를 구하면 되는 문제다. 단, 모든 벽마다 탐색을 해서 이동할 수 있는 칸 개수를 구하면 시간 초과가 발생한다. 예를 들어 다음과 같은 케이스가 들어온다고 해보자. 예시: 6 6 101010 000000 101010 000000 101010 000000 1에서 탐색을 시작할때마다 모든 0의 개수를 반복적으로 구하기 때문..
프로그래밍/Algorithm
문제 https://www.acmicpc.net/problem/17081 17081번: RPG Extreme 요즘 택희는 RPG 게임을 하고 있다. 던전을 헤쳐나가며 몬스터를 물리치고, 아이템을 모으고, 레벨 업을 하여 보스 몬스터를 물리치는 전형적인 RPG 게임이다. 이 게임은 N×M 2차원 그리드 위에서 www.acmicpc.net 풀이 방법 문제의 설명이 길지만 설명 그대로 구현하고 시뮬레이션 돌리면 되는 문제다. 옛날 로그 게임 마냥 진행되는데 처리 해줘야 하는 케이스가 많아서 일일이 다 따져보고 구현하고 오류가 날 경우 테스트해봐야 한다. 내 경우 어려웠던 케이스는 다음과 같다. 그리드 출력 시 승리 또는 패배 여부에 따른 플레이어의 출력 및 위치 이동 명령 문자열 S가 끝났을 때, 진행된 턴 ..
문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 방법 그래프 탐색을 활용한 구현 문제다. 주의해야 할 것은 시작부터 덩어리가 이미 분리되어 있는 케이스가 있기 때문에 녹이기 전에 먼저 덩어리 개수를 확인해줘야 한다. 따라서 현재 빙산의 높이 정보를 토대로 빙산의 덩어리가 두 덩어리 이상이면 현재 시간을 출력하고, 그렇지 않다면 문제의 설명대로 빙산을 녹이고 시간을 증가시키면 된다. 빙산의 덩어리 개수를 세는 알고리즘은 BFS나 ..
문제 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 풀이 방법 2206번 벽 부수고 이동하기와 비슷한 문제다. 이 문제에서는 벽을 K개만큼 부술 수 있는게 차이점이다. 비슷하게 풀되 벽을 1개까지 부쉈던 부분을 K개까지 부술 수 있게 처리하면 된다. 코드 #include #include #include #include #include #include using namespace std; int dy[] = ..
