본문 바로가기

분류 전체보기

BOJ_7569 토마토 문제는 익은 토마토와 인접한 익지 않은 토마토가 하루 뒤에 익는다고 가정하고 모든 토마토가 익을 때 까지 걸리는 시간을 출력하는 문제이다. 특별히 어려운 부분은 없고, 축이 3개이다보니 인접한 토마토를 찾는 좌표쌍의 경우를 잘 찾기만 하면 될 것 같다. #include using namespace std; typedef struct _def { int x; int y; int z; } def; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int m, n, h, tmp, left = 0, day = 0; int dx[6] = { -1,0,1,0,0,0 }; int dy[6] = { 0,1,0,-1,0,0 }; in..
BOJ_1012 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 지렁이는 인접한 배추를 옮겨다닐 수 있을때, 모든 배추를 커버하기 위해서 몇마리의 지렁이를 풀어야하는지 묻는 문제이다. 전에 풀었던 그림 문제와 똑같은 문제나 다름없다. 이중for문을 사용해서 밭의 좌표를 이동하며 BFS를 시행하면 된다. 배추가 심어져있으면서 방문하지 않았던 좌표가 생길때마다 값을 1씩 더해서 결과로 출력하면 된다. #include #include #define X first #define Y second using namespace std; int mai..
BOJ_1697 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 0부터 100,000 까지의 좌표상에서 수빈이가 동생을 찾는 문제이다. 수빈이는 +1, -1, *2의 위치를 가질 수 있다. 지금까지 풀었던 BFS문제와는 다른 형태를 가지고 있지만, 그렇게 어렵지 않게 구현할 수 있을것같았다. -1 연산을 했을때 0보다 작아지거나 *2연산을 했을때 동생의 위치보다 큰 값을 갖는 경우는 값을 푸시하지 않도록 했다. #include #include using namespace std; int main(v..
BOJ_4179 불! 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 지훈이의 위치와 불의 위치가 주어지고 탈출가능 여부와 최단탈출시간을 구하는 문제이다. 처음 문제를 읽었을때 표현이 애매해서 잘 이해가 되진 않았는데, 출처에서 공개한 테스트케이스를 보니 이해가 되었다. 구현방법은 먼저, 불이 BFS를 실행하면서 date배열에 걸리는 시간을 넣었다. 이후 지훈이 BFS를 실행하고 새로운 위치에서의 시간 값이 불BFS에서 저장한 값보다 작다면 값을 바꾼다. 이후 큐에 위치값을 푸시해준다. 미로가 n*m크기일때 만약 큐..
BOJ_7576 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 익은 토마토에 인접한 토마토는 하루 뒤면 익는다. 모든 토마토가 익는 날까지 걸리는 시간을 출력하는 문제. 시작점이 여러개인 BFS라고 할 수 있는데, 처음에는 익은 토마토의 좌표에서부터 BFS를 각각 실행하려고 했다. 그러면 겹치는 부분이 생길것이고 다시 비교연산을 해서 원래 들어있던 시간값보다 작으면 값을 바꾸는 방법을 떠올렸는데, 다시 생각해보니 너무 비효율적인 것 같았다. 모두 익은 토마토가 주어진다면 주어진 크기만큼 BFS를 반복하는 것..
BOJ_2178 미로탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N*M 크기의 미로에서 (0,0) -> (N,M) 까지 도달하기 위한 거리를 측정하는 문제 처음 문제를 보고 고려했던 부분은 갈림길이 나오면 어떻게하지? 라고 생각했다. 말로 표현하기는 조금 어렵지만 사방으로 번져 나가고 이때마다 거리를 1씩 더해주면 되겠다고 생각하고 코드를 짰다. #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); str..
BOJ_1926 그림 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 기본적인 BFS문제 처음 BFS를 다뤄보다 보니 구현 자체에 시간을 조금 오래 썼다 고려해야 할 사항으로는 1. (0,0) 위치가 1이 아닐수도 있다. 2. 끊어져있는 그림을 찾아내기 위한 방법을 고안해야한다. 3. 그림의 크기와 갯수를 세야한다. 1, 2번의 경우에는 이중 for문을 사용하여 (0,0)위치부터 행,열의 숫자를 더해가며 검증을 하는 방식을 통해 해결할 수 있었다. 3번의 경우 while문에 새로 들어오는 경우 새로운 그림이므로 개수를 1개씩 더해주고,..
BOJ_20540 연길이의 이상형 20540번: 연길이의 이상형 졸업을 앞둔 연길이는 크리스마스가 다가올수록 외로움을 느낀다. 그런 연길이를 위해 동우는 소개팅을 시켜주지는 않고 연길이의 이상향을 찾는 것을 도와주고자 한다. MBTI 신봉자인 연길이는 www.acmicpc.net 입력받은 MBTI와 반대의 MBTI를 출력하는 문제 처음에는 그냥 if문으로 하나씩 처리할 생각이었지만, 다른 풀이방법을 생각하다가 배열을 사용한 방법으로 구현함. #include using namespace std; int main() { char arr[4][2] = { {'E','I'}, {'S','N'}, {'T','F'}, {'J','P'} }; string mbti; cin >> mbti; for (int i = 0; i < 4; i++) { if (..

티스토리툴바