빅맥좋아요

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 백준 2206번 벽 부수고 이동하기를 풀어봤습니다. 기존 BFS문제에 벽을 부술 수 있는 상태가 추가됐습니다. 처음엔 벽을 부수고 이동하는 것과 안부수고 이동하는 것에 차이를 안두고 풀었더니 문제가 생겼습니다. 그래서 이동 거리를 저장하는 check배열과 방문한 적 있는지 확인하는 visited배열에도 상태를 추가해서 3차원 배열로 만들었습니다. 벽을 부술 수 있으면 1,..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 백준 9184번 신나는 함수 실행을 풀어봤습니다. 간단한 DP문제입니다. 한번 연산했던 인풋이 들어오면 dp배열을 참조해서 연산없이 return 값을 구합니다. 아래는 전체 코드입니다. #include using namespace std; #define PAD 50 int dp[101][101][101]; int w(int a, int b, int c) { if (dp[PAD+a][PAD + b][P..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 백준 1697번을 풀어봤습니다. 문제 형식이 토마토랑 다르지만 똑같이 BFS로 풀 수 있습니다. 상하좌우 대신 한 칸 앞으로 이동, 한 칸 뒤로 이동, 두 배 앞으로 이동 3개의 좌표를 이용하면 됩니다. 아래는 전체 코드입니다. #include #include #include #include using namespace std; int n, k; int map[10000..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 백준 7569번 토마토를 풀어봤습니다. 기존 2차원 BFS문제에서 3차원으로 바꼈습니다. 변수가 3차원인것만 제외하면 2차원과 푸는 방법이 똑같습니다. 아래는 전체 코드입니다. #include #include #include #include using namespace std; int m, n, h; int map[100][100][100]; int check[100][10..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 백준 1003번을 풀어봤습니다. 간단한 다이나믹 프로그래밍 문제입니다. 재귀 함수를 그대로 사용하면 시간이 너무 오래걸려서 결과값을 저장하는 배열을 만들어주면 됩니다. 재귀 함수 첫 부분에 이미 계산한 값인지만 체크해주는 if문만 만들면 됩니다. 아래는 전체 코드입니다. #include using namespace std; int callCount[40][2]; pair fibonacci(int n) { if (callCount[n][0] != 0 || callCount[n][1] != 0) ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 백준 7576번 토마토 문제를 풀어봤습니다. BFS로 풀었습니다. 아래는 전체 코드입니다. #include #include #include #include #include using namespace std; int m, n; bool visited[1000][1000]; int map[1000][1000]; int check[1000][1000]; int dx[4] = { -1,..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 백준 2178번 미로찾기를 풀어봤습니다. 최단경로를 찾을 때 BFS를 사용합니다. 아래는 전체 코드입니다. #include #include #include #include using namespace std; bool visited[100][100]; int map[100][100]; int depth[100][100];// Distance int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,-1,0,1 ..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 백준 1012번 유기농 배추를 풀어봤습니다. 테스트케이스를 반복할 때마다 visited와 map배열을 초기화 해줘야합니다. DFS 알고리즘으로 간단하게 풀 수 있습니다. 아래는 전체 코드입니다. #include #include #include using namespace std; bool visited[50][50]; int map[50][50]; int t, m, n, k; int dx[4] = { -1,0..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 백준 2667번 단지번호붙이기를 BFS로 풀어봤습니다. 입력이 최대 25자까지 가능해서 string으로 입력을 받았습니다. 단지가 25x25이고 단지의 상하좌우를 체크할 때 오류가 없도록 배열을 27x27로 잡았습니다. 그래프의 정점을 좌표가 되도록 만들었습니다. 아래는 전체 코드입니다. #include #include #include #include #include using namespace s..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 백준 2606번 바이러스를 풀어봤습니다. 아래는 전체 코드입니다. #include #include #include #include using namespace std; bool visited2[1001];// For BFS vector graph[1001];// Graph queue q;// For BFS void BFS(int v); int main() { int n, edge, start; cin ..