컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 해결 알고리즘 BFS에서 0인 부분에 갈 때는 cnt를 1 더해주고, 만약 원래 있던 값보다 작으면 갱신해준다. 소스 코드 #include #define MAX_SIZE 101 using namespace std; int n; int arr[MAX_SIZE][MAX_SIZE], result[MAX_SIZE][MAX_SIZE]; int dir[4][2] = {{-1, 0}, {1, 0}, {0..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 해결 알고리즘 빙산의 위치를 따로 받아서 바로바로 빼고 다해주는 방식으로 해야 시간초과를 피할 수 있다. 옆에 바다가 있다고 바로 빙산에서 빼주지 말고 따로 배열을 만들어서 거기에 뺄 값을 저장해두고 for문이 끝나면 한 번에 빼줘야 문제에서 원하는대로 빙산이 녹는 걸 구현할 수 있다. BFS를 이용해 두 가지로 나누어졌다면 년도를 출력해준다. 아니면 0을 출력함. 소스 코드 #incl..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 해결 알고리즘 bfs로 푸는 문제 시작점과 끝점이 같은 걸 예외처리 안 해줘서 계속 틀렸다.. 소스 코드 #include using namespace std; int F, S, G, U, D; bool visited[1000002]; void bfs(){ queue q; q.push({S, 0}); visited[S] = true; if(S == G) { cout > S >> G >> U >> D; if..

https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 문제 해결 알고리즘 전형적인 bfs문제였다. 소스 코드 #include using namespace std; int result = 0; int start_x, start_y; int N, M; char arr[602][602]; bool visited[602][602]; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool isIn(i..

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 문제 해결 알고리즘 BFS를 할 때 탐색 한 수를 중점으로 탐색을 해주면서 결과값에 제곱으로 더해준다. (이 때 적군과 아군을 구분해준다.) 소스 코드 #include using namespace std; int N, M; int W_result = 0, B_result = 0; char arr[101][101]; int visited[101][101]; int dir[4..

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 문제 해결 알고리즘 벽 부수고 이동하기 1에서 했던 걸 갯수만 늘려주는 식으로 배열도 늘려주고 벽 부술 수 있는 개수도 늘려준다. https://kimmessi.tistory.com/134 소스 코드 #include #define MAX 1001 using namespace std; int graph[MAX][MAX]; int visited[MAX][MAX][1..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 해결 알고리즘 좀 까다로운 BFS문제였다. 벽을 부술 수 있는지 없는지의 여부를 판단하기 위해 삼중배열의 visited배열을 선언해준다. 벽을 부수면 [0]으로 가고 벽을 부수지 않았을 때는(벽을 부술 수 있을 때) [1]에서 bfs를 진행해준다. ( 이 때 N == 1이고 M == 1이면 -1이 출력되지 않게 조심해주어야한다 ) 소스 코드 #include #defi..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 문제 해결 알고리즘 3차원으로 하는 BFS. 딱히 특별한 건 없다. 소스 코드 #include #define MAX 40 using namespace std; int L, R, C; char building[MAX][MAX][MAX]; int visited[MAX][MAX][MAX]; int dir[6][3] = {{-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0,..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제 해결 알고리즘 BFS를 해주는데 육지인 모든 칸들을 전부 한 번씩 BFS를 해준다. 소스 코드 #include using namespace std; int R, C, result = 0; int arr[51][51]; int visited[51][51]; int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; void Clear(){ for(int i=0;i

https://www.acmicpc.net/problem/17267 17267번: 상남자 CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하 www.acmicpc.net 문제 해결 알고리즘 왼쪽, 오른쪽으로 갈 수 있는 갯수를 전부 포함한채 BFS를 설계해준다. 이 때, 상하 움직임은 무제한이므로 상하로 움직일 땐 한 번에 전부 탐색해서 큐에 넣어준다. 그렇지 않으면 예외가 발생한다. 소스 코드 #include #define MAX 1001 using namespace std; int arr[MAX][MAX]; bool visited[MAX][MAX]; int N, M..