[정답 코드] c++ #include #include #include #include using namespace std; typedef struct { int speed; //속도 int d; //방향 1:상,2:하,3:우,4:좌 int z; //크기 }info; //상어 정보 int R, C; //R - 세로y, C - 가로x int M; //초기 상어 수 vector map[101][101]; //어장~!~! vector temp[101][101]; int answer = 0; //잡은 물고기의 합. void print() { cout
분류 전체보기
[정답 코드] #include #include #include #include #include using namespace std; const int MAX = 100000000; //디버깅용 프린트 함수 void print(vector&v) { int s = v.size(); for (int i = 0; i < s; i++) { cout
지저분 그자체 [정답 코드] #include #include #include #include using namespace std; //디버깅용 프린트함수 void print(vector&v) { for (int i = 0; i N >> L; M = N; //map 이차원 배열 선언 vector map(N, vector(M)); for (int i = 0; i > map[i][j]; } } //가로방향 탐색 for (int i = 0; i < N; i++) { find(map[i]); } //세로방향은 어떻..
[정답코드] #include #include #include #include using namespace std; const int MAX = 9; //int map[MAX][MAX]; int N, M; vector virus; //y,x int dy[4] = {-1,1,0,0}; int dx[4] = {0,0,-1,1}; int ans=-1; int count_safe(vector& v) { int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (v[i][j] == 0) cnt++; } } return cnt; } void dfs(vector&v) { queue q; for (int i = 0; i < virus.size..
[문제] 1) 정수 A, B가 주어졌을 때, *2 혹은 1을 추가하는 연산을 통해 A->B까지 가는 것이 목표. 2) 이 때,연산의 수행해야하는 연산 횟수의 최솟값을 구해라. ▷ 입력 : A, B (최대 10^9) [풀이] 1) 기본적으로 comma6oz.tistory.com/10 (숨바꼭질) 문제와 탐색방법은 유사하다. 2) bfs로 탐색하고 queue에 현재 노드와 연산 횟수를 저장한다. ▷ 현재 노드가 B가 되면 탐색을 종료하고 연산 횟수 반환한다. 3) 숨바꼭질 문제와 다르게 최대값이 매우 크므로 vector를 만들어서 거리 값을 저장하면 메모리 초과가 발생한다. ▷ vector을 이용해 BOJ에 제출했을 때 bad_alloc과 OutofBounds가 발생했다. ▶ 메모리 초과 해결 방법 ▷ in..
[문제] - M*N크기 배열에 토마토 정보가 주어진다. (1=익음, 0=안 익음, -1=없음) - 익은 토마토에 인접한 곳에 있는 토마토는 다음날 익는다. - 며칠이 지나야 모든 토마토가 익을 것인가 - 입력 : M,N, M*N배열 정보 - 출력 : 날짜 [풀이] - bfs로 배열을 탐색한다. (기본 껍데기 활용) - q.front()로 현재 노드를 설정하고 상하좌우 노드를 탐색한다. => 이 때, 날짜를 계산하기 위해 map[next]의 값을 map[cur]+1로 해준다. - 마지막에 map의 최댓값-1을 하면 모든 토마토가 익는 날짜를 알 수 있다. - bfs가 끝나고 map에 0이 남아있으면 다 익지 않은 것이므로 -1로 예외처리 필요. - 틀린 원인 : 배열을 입력 받을 때 m,n 헷갈려서.. [..
[문제] - M*N배열에 0,1을 입력하고 이어진 1의 묶음을 찾아내는 것 - 아래 그림처럼 이어진 1의 묶음을 세보면 5개 => bfs로 풀자 [풀이] - 기본 bfs알고리즘에서 시작 노드를 for문을 통해 새로 정해주면서 돌린다~ - 이미 방문했거나 0인 노드는 탐색 x - 주의) 테스트케이스마다 map과 vis를 memset으로 초기화해줘야된다. 까먹고 안했다가 틀림! [코드] #include #include #include #include using namespace std; #define X first #define Y second int M, N, K; const int MAX = 51; int map[MAX][MAX]; bool vis[MAX][MAX]; int ans = 0; int dx[..
[문제] - 수빈이 위치 N, 동생 위치 K로 나타낼 수 있다. (0 node+1, node-1, 2*node - 위의 3개 노드를 bfs방식으로 탐색한다. - node 또는 next가 map의 범위를 벗어나거나 node가 k, 즉 동생 위치에 도달했을 경우 continue * 런타임에러 발생 원인 : node 예외처리만 해주고 next에 대해서 처리를 안해줘서 발생 [코드] #include #include #include #include using namespace std; const int MAX = 100001; int n, k; vector map[MAX]; bool vis[MAX]; //방문 여부 확인 int dist[MAX]; //거리(초) 저장 void bfs(int start) { //초기..
[코드 참조!!!!!!!] blog.encrypted.gg/941?category=773649 [문제] - N*M 크기의 미로가 주어지고 갈 수 있는 길이 0과 1로 표시된다. 가로,세로로 인접한 칸으로만 이동이 가능하다. 이 때, 미로의 (1,1)위치에서 (n,m)까지 최소 거리를 계산하여 출력하는 문제이다. - 입력 : n, m (미로 크기 1 n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { //띄어쓰기 없이 입력받을 때 사용 int temp; scanf("%1d", &temp); map[i][j] = temp; } } //bfs탐색에 사용할 queue선언 queueq; check[0][0] = 1; dist[0][0] = 1;..
문제 재정의 수열S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력해라 입력 수열S의 크기(1~20), 수열S{...} 출력 가장 작은 자연수 k 풀이 1) 재귀함수를 이용해 가능한 모든 부분수열의 합을 저장 (vector allSum) 2) sort,unique함수로 allSum을 정렬하고 중복 요소 제거 3) allSum이 연속된 값을 가지지 않을 때 요소가 답이므로 출력 4) 만약 합의 첫번째 요소가 1이 아니면 무조건 1이 답이다.. 가장 작은 자연수는 1이니께 #include #include #include using namespace std; int N; int num[20]; vector allSum; void go(int idx, int sum) { if (idx == N) {..
