https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net BFS문제다. 일반 미로 문제에서 벽(검은방)을 부수고 갈 수 있는 미로로 생각하면 되는 문제다. 문제에서 구해야하는 건 미로의 최단 경로가 아닌 최대한 벽을 적게 만나는 경로를 찾는 것이다. 방문 배열을 이용해서 문제를 해결했다. 방문 배열에 지나간 검은 방의 개수를 저장하고 현재 이동하려는 방 까지의 검은 방의 개수가 이전에 방문했을 때의 검은 방의 개수보다 작다면 방문한다. 이 때 간과했던 ..
BFS
https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net BFS 문제다. DFS도 가능할 것이라고 생각하나 BFS로 접근했다. 구현 요소도 포함된 것 같다. 재방문이 필요하다는 점에서 고민 요소가 있었다. 조건 없이 계속 재방문 하면 무한 루프가 돌거나 돌지 않아도 메모리가 터질 것이다. 무한 루프를 막기 위해 방문 시 들고 있던 돈을 기준으로 재방문 여부를 결정했다. 방에 들어와서 소지하게 된 돈이 이전에 방문했을 때의 돈을 비교해서 ..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 문제다. https://abbiddo.tistory.com/12 불!과 비슷한 문제다. 같은 상황에 출구가 정해져 있고, 돌이 있다는 점에서만 차이가 있기 때문에 설명은 생략 #include #include using namespace std; int n, m; char board[50][50]; bool gisit[50][50];// 고슴도치의 방문 체크 bool wisit[50][50];// 물의 ..
https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net BFS와 구현 문제다. BFS와 동일하게 진행하고, 움직일 때 범위 검사만 추가해서 했다. 회전에 대해서는 방문 배열을 3차원으로 생성해 가로일 때 방문과 세로일 때 방문을 구분해서 체크했다. 회전시 계산이 편하도록 3칸 중 중간 칸을 기준으로 삼았다. #include #include using namespace std; // 상하좌우 탐색을 위함 int dr[4] = { ..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net BFS 문제다. 말이 되고픈 원숭이와 비슷하다. https://abbiddo.tistory.com/16 만날 때마다 새롭다. 특수 경우가 방문한 곳을 일반적인 경우로 방문할 수 있어야 한다는 점이 항상 헷갈리게 한다. 방문 배열을 3차원으로 만들고 [r][c][0]에는 벽을 뚫고 가지 않은 경로 / [r][c][1]에는 벽을 뚫고 간 경로를 저장했다. 초기값은 벽이 아니기..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net BFS 문제다. 문제를 해결하기 위해 돌아온 길이 많아서 시행착오는 후에 작성하겠다. 문제 해결은 일반 BFS에 8방향 검사를 추가로 시행했다. 방문 배열을 3차원으로 설정해 8방향 이동 능력을 몇 번 사용했는지 체크했다. 간단한데도 이 방법을 생각해내는데 오래 걸렸다... 그리고 이 문제에서 오류가 발생하기 쉬운 점은 입력이 세로 가로가 아닌 가로 세로인 점이다. 세로를 먼저 입..
