#include #include #include #include #include #include #include #include #include #include #include #include #define MAIN 105 //#define CUT 20091024 -> 분할 정복 제곱수 출력 //#include //#include //#include /*절대값(fabs), 제곱근(sqrt), 거듭제곱(pow), 올림(ceil), 버림(floor) 삼각비(cos, sin, tan), 로그(log), 반올림(round) ...등등 입력된문자수(strlen), 대문자인지 확인(isupper), 소문자인지 확인(islower) 알파벳인지 확인(isalpha), 숫자문자인지 확인(isdigit), 숫자 또는 영문자인지 확인(isalnum) 소문자->대문자(toupper), 대문자->소문자(tolower) 공백을 포함한 문자열입력(fgets) -> ex)) fgets(str, 101, stdin) > stdin은 언제나 써야됨 문자열의 길이 (strlen), a <- b 복사 (문자열 strcpy(a, b)), ******a문자열 뒤에 b문자열 복사(strcat(a,b)) a와 b크기 비교 (strcmp(a, b)) --> 같으면 0 / a가 더 크면 (아스키코드) 양수 / b가 더 크면 음수 a문자열에 c문자가 포함되어있는지 (strchr(a, c)), a문자열에 b문자열이 포함되엇는지 (strstr(a, b)) strchr과 strstr 두 함수 다 조건에 만족되면 0이 아닌 수 a문자열에 b문자열의 앞부분 n개의 문자를 복사한다. (strncpy(a, b, n)) a문자열 뒤에 b문자열을 n개만큼 연결하여 복사한다 (strncat(a, b, n)) a와 b의 문자열에서 n개의 크기를 비교한다. (strncmp(a, b, n)) 위의 strncmp은 같으면 0 / a가 더 크면 (아스키코드) 양수 / b가 더 크면 음수 문자열의 처음부터 정수에 해당하는 부분을 정수로 변환하여 준다 (atoi(?)) --> ?은 문자열 이름 문자열의 처음부터 실수에 해당하는 부분을 실수로 변환하여 준다 (atof(?)) --> ?은 문자열 이름 변수들의 내용 전체를 서로서로 붙여서 문자열 ??에 저장한다. sprintf(??, "%d ..", ?, ? ..) ?은 변수들의 이름이다. ex )) sprintf(str, "%.2lf%.2lf", a, b) --> str = "%.2lf%.2lf", a, b; %lf 대신에 %d도 넣을 수 있으며 %d %d 이런 식으로 변수들 사이에 공백을 넣으면 "%d %d" --> a b가 된다 struct 구조체 -> 정수, 소수, 문자, 문자열를 넣을 수 있다 cin == scanf ex)) cin >> str; str를 입력받아라 string 문자열 선언 역수 출력 void p(int x) { if(x == 0) return; printf("%d", x % 10); p(x / 10); } 소수인지 아닌지 리턴 (합성수면 0리턴, 소수면 1리턴) bool is(int x) { for(int i = 2; i <= x / i; i++) { if(x % i == 0) return false; } return true; } 최대공약수 구하기 int g(int x, int y) { if(y == 0) return x; return g(y, x % y); } cin>>str는 string str를 공백이 입력되기 전까지 입력받는 함수입니다. string str는 문자열 str를 선언하는 겁니다. cout< 변수 이름; - 후입선출 변수 이름.push(넣을 숫자); -> stack에 넣을 숫자를 넣기 변수 이름.pop(); -> stack의 맨 마지막꺼 빼내기 변수 이름.top() -> stack의 맨 마지막꺼 변수 이름.size(); -> stack의 자료 개수 using namespace std; 한칸 밑에 queue<선언 타입> 변수 이름; - 선입선출 변수 이름.push(넣을 숫자); -> queue에 넣을 숫자를 넣기 변수 이름.pop(); -> queue의 맨 처음꺼 빼내기 변수 이름.front() -> queue의 맨 처음꺼 변수 이름.size(); -> queue의 자료 개수 stack 해더 파일은 , queue는 이다. 이진탐색 1. 현재 탐색 구간의 가운데 배열번호(인덱스) mid를 구한다. mid = (low + high) / 2; 2. A[mid]값과 target값을 비교한다. (1) 만약 A[mid] == target 이라면 목표값 또는 목표값이 있는 위치를 찾은 것이다. (2) 만약 A[mid] < target 이라면 low = mid+1로 하여 검색범위를 조정한다. (3) 만약 A[mid] > target 이라면 high = mid-1로 하여 검색범위를 조정한다. 3. 탐색구간이 남아 있고 목표값을 찾지 못한 동안 1, 2번 프로세스를 반복한다. 만약 low > high 라면(탐색구간이 남지 않는 경우) 목표값이 배열에 없는 경우이다. 퀵소트 1. low >= high 라면 현재 구간은 정렬된것으로 본다. 2. 분할(Divide) 과정 구간내의 임의의 원소를 pivot값으로 정한다. 여기서는 pivot = A[high]로 한다. 1) pivot 이하의 값들을 배열의 왼쪽에 pivot 이상의 값들을 오른쪽에 배치시킨다. 2) pivot 의 자리를 찾아준다. i = low-1; for (j=low; j < high; j = j+1){ if ( A[j] < pivot) swap(A[ ++i], A[j]); } swap(A[++i], A[high]); /// pivot 자리찾기 3. 정복(Conquer) 과정 pivot을 기준으로 왼쪽과 오른쪽을 재귀호출하여 정렬시킨다. 합병정렬 (Merge Sort) 정렬할 배열을 A[], 구간의 시작 인덱스(배열번호)를 low, 끝 인덱스를 high 라고 하자. 1. low >= high 라면 현재 구간은 정렬된것으로 본다. 그렇지 않은 경우 2. 분할(Divide) 과정 : 구간의 중앙을 구한다. mid = (low + high) / 2; 3. 정복(Conquer) 과정 : 나누어진 두 구간을 각각 재귀적으로 정렬한다. 4. 결합(Merge) 과정 : 정렬된 두 구간을 이용하여 정렬된 하나의 구간을 만들어 임시 배열 B[]에 저장한다. 5. 복사(Copy)과정 : 결합이 완성된 임시 배열 B[]를 A[]에 복사한다. *정렬은 'sort(배열 이름 + 시작 위치, 배열 이름 + (끝 위치 + 1));'로 간편하게 사용할 수 있다 'reverse(배열 이름 + 시작 위치, 배열 이름 + (끝 위치 + 1));'는 배열을 뒤집을 수 있다. 연산자 오버로딩 bool operator<((구조체 이름) (이름)) { return (비교); } -> '<'라는 표현이 쓰이면 발동된다. ex) struct Student { char name[20]; int age; double height; bool operator<(Student right) { return age Student 구조체끼리의 비교에서 '<'가 쓰이면 age끼리 비교한다. vector<타입> (변수 이름); : <타입형> (변수이름) 선언 ex ) vector A; (만약 A[n]라면 2차원 배열 = A[n][무한]) (만약 타입이 vector라면 A[무한][무한] (백터 이름).push_back((넣을것)); : 백터에다가 (넣을것) 넣기 (int)(백터 이름).size() : 백터 크기 (백터 이름).pop_back() :마지막꺼 터트리기 (크기가 0이면 터짐) (백터 이름).resize() : A.resize(n, a); - > A의 n번째까지 a로 채우기 or A의 n번째까지 지우기 ex ) A가 [1,2,3,4]일때, A.resize(6) -> [1,2,3,4,0,0] A.resize(6, 1) -> [1,2,3,4,1,1] A.resize(2) -> [1,2] (백터 이름).front() = n; 백터의 맨앞의 값을 n으로 바꿈 (백터 이름).back() = n; 백터의 맨뒤의 값을 n으로 바꿈 (백터 이름).front()++; 백터의 맨앞의 값을 1을 더함 (백터 이름).back()++; 백터의 맨뒤의 값을 1을 더함 (front, back 둘 다 사칙연산 다 됨) (백터 이름).empty() : 백터가 비어있으면 true, 아니면 false sort((백터이름).begin(), (백터이름).end()); -> 정렬 (백터이름).begin() : 백터의 시작 인덱스 -> for, while문 등 XX (백터이름).end() : 백터의 끝 인덱스 -> for, while문 등 XX reverse도 똑같음 for(int element: arr) printf("%d " , element); ///arr 배열의 각 원소 element에 대하여 dfs 함수 void dfs(int n) { if(A[n].size() == 0) { return; } for(int i = 0; i < A[n].size(); i++) { if(t[A[n][i]]) { cout << A[n][i] << " "; t[A[n][i]] = false; dfs(A[n][i]); } } } //t는 중복함수 백터 정렬 sort(A[i].begin(), A[i].end()); bfs void bfs() { queue q; q.push(V); while(!q.empty()) { int f = q.front(); cout << f << " "; t[f] = false; q.pop(); for(int i = 0; i < A[f].size(); i++) { if(t[A[f][i]]) { q.push(A[f][i]); t[A[f][i]] = false; } } } } dfs 영역 void moving(int x, int y) { if(x <= n &&p[x + 1][y]) { p[x + 1][y] = false; moving(x + 1, y); } if(x >= 1 && p[x - 1][y]) { p[x - 1][y] = false; moving(x - 1, y); } if(y <= n && p[x][y + 1]) { p[x][y + 1] = false; moving(x, y + 1); } if(y >= 1 && p[x][y - 1]) { p[x][y - 1] = false; moving(x, y - 1); } } int 하나 = 4bt 1mb = 1024kb 1kb = 1bt n.resize(N + 1, vector(N + 1)) 2차원 n vector resize vector> (name); -> pair형 vector 선언 (name).(first or second); (name).push_back({(값), (값)}); -> pair 형 push_back feel((변수 이름) + (시작 위치), (변수 이름) + (끝 위치), (채우려는 것)); */ using namespace std; int N, M, p[1000 + 5][1000 + 5]; int pp[1000 + 5][1000 + 5]; int t[1000000 + 5][2 + 5], k = 0; void bfs() { queue> q; for(int i = 0; i < k; i++) { q.push({t[i][0], t[i][1]}); } pair f = q.front(); int x = f.first, y = f.second; pp[x][y] = 0; while(!q.empty()) { pair f = q.front(); q.pop(); int x = f.first, y = f.second; if(x + 1 <= M && p[x + 1][y] == 0 && pp[x + 1][y] == -1) { p[x + 1][y] = 1; pp[x + 1][y] = pp[x][y] + 1; q.push({x + 1, y}); } if(x - 1 >= 1 && p[x - 1][y] == 0 && pp[x - 1][y] == -1) { p[x - 1][y] = 1; pp[x - 1][y] = pp[x][y] + 1; q.push({x - 1, y}); } if(y + 1 <= N && p[x][y + 1] == 0 && pp[x][y + 1] == -1) { p[x][y + 1] = 1; pp[x][y + 1] = pp[x][y] + 1; q.push({x, y + 1}); } if(y - 1 >= 1 && p[x][y - 1] == 0 && pp[x][y - 1] == -1) { p[x][y - 1] = 1; pp[x][y - 1] = pp[x][y] + 1; q.push({x, y - 1}); } // for(int i = 1; i <= M; i++) { // for(int j = 1; j <= N; j++) { // cout << p[i][j] << " "; // } // cout << "\n"; // } // cout << "\n"; } int ans = -1; for(int i = 1; i <= M; i++) { for(int j = 1; j <= N; j++) { ans = max(pp[i][j] , ans); if(p[i][j] == 0) { cout << "-1"; return; } } } cout << ans; } int main() { cin >> N >> M; for(int i = 0; i <= 1000; i++) { for(int j = 0; j <= 10000; j++) { pp[i][j] = -1; } } for(int i = 1; i <= M; i++) { for(int j = 1; j <= N; j++) { cin >> p[i][j]; if(p[i][j] == 1) { t[k][0] = i; t[k++][1] = j; } } } bfs(); return 0; }

제출 #35979

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: