-
백준 1743번 : 음식물 피하기 (C 언어)c c++ 언어 공부 2023. 10. 28. 16:26
https://www.acmicpc.net/problem/1743
1743번: 음식물 피하기
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다
www.acmicpc.net
Code:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <stdio.h>#include <limits.h>int n, m, k;int arr[101][101] = { 0, };int check[101][101] = { 0, };int dx[] = { -1,1,0,0 };int dy[] = { 0,0,-1,1 };int max = INT_MIN;int count = 0;void dfs(int y, int x){check[y][x] = 1;count++;for (int a = 0; a < 4; a++){int yn = y + dy[a];int xn = x + dx[a];if (yn >= 1 && yn <= n && xn >= 1 && xn <= m && check[yn][xn] == 0 && arr[yn][xn]==1){dfs(yn, xn);}}}int main() {scanf("%d %d %d", &n, &m, &k);int r, c;for (int i = 0; i < k; i++){scanf("%d %d", &r, &c);arr[r][c] = 1;}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (arr[i][j] == 1&&check[i][j]==0){count = 0;dfs(i, j);if (max < count){max = count;}}}}printf("%d", max);}cs 문제 설명:
코레스코 콘도미니엄 8층은 학생들이 식사를 하는 공간인데, 학생들 중 일부가 음식물을 통로에 떨어뜨리는 문제가 발생합니다. 이 음식물들은 주위에 뭉치게 되어 큰 음식물 쓰레기가 됩니다. 이 문제에서는 통로에 떨어진 음식물 중 가장 큰 음식물의 크기를 찾는 것이 목표입니다.
입력:
- 첫 번째 줄에는 통로의 세로 길이 N, 가로 길이 M, 그리고 음식물 쓰레기의 개수 K가 주어집니다.
- 다음 K개의 줄에는 음식물이 떨어진 좌표 (r, c)가 주어집니다.
좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터를 기준으로 합니다. 입력으로 주어지는 좌표는 중복되지 않습니다.
코드 설명:
- 먼저, 입력으로 주어진 통로의 크기와 음식물의 좌표를 입력 받습니다.
- 이차원 배열 "arr"을 이용하여 음식물이 떨어진 위치를 표시하고, "check" 배열을 이용하여 해당 위치를 이미 방문했는지 여부를 확인합니다.
- DFS 함수는 주어진 좌표로부터 상하좌우로 탐색하여 연결된 음식물의 크기를 계산합니다. 방문한 위치는 "check" 배열을 통해 표시하고 "count" 변수로 음식물의 크기를 저장합니다.
- 이중 반복문을 사용하여 모든 좌표를 확인하면서 음식물이 있고 아직 방문하지 않은 경우, 해당 영역을 DFS로 탐색하여 가장 큰 음식물 영역의 크기를 찾습니다.
- 가장 큰 음식물 크기를 "max" 변수에 저장하고 출력합니다.
'c c++ 언어 공부' 카테고리의 다른 글
백준 2523번 : 별 찍기 - 13 (C 언어) (0) 2023.10.30 백준 29634번 : Hotel (C 언어) (1) 2023.10.29 백준 : 16486번 : 운동장 한 바퀴 (C 언어) (0) 2023.10.27 백준 1267번 : 핸드폰 요금 (C 언어) (0) 2023.10.26 백준 13565번 : 침투 (C 언어) (0) 2023.10.25