DFS로 25개 중 7개를 고르는 조합을 만든다. 7개 원소를 골랐으면 그 중에 4명 이상이 이다솜파인지, 인접한지 확인한 후 ans를 올려준다. 번호를 0~24번까지 붙이면 y좌표는 해당 번호/5, x좌표는 해당 번호%5로 검사하면 된다. 복사 배열을 하나 더만들어서 조합으로 뽑은 위치에는 Z로 표시해줬다. 뽑은 수 중 하나 아무거나 넣은 후 근접 BFS를 돌렸을 때 Z의 총 개수가 7이 나오면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; string student[5][5]; string carr[5][5]; bool visit[5][5]; int ypos[] = ..
풀이 참고 https://yabmoons.tistory.com/319 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #define endl "\n" #define MAX_N 10001 using namespace std; typedef struct st { int num; int parent; int child[2]; int index;//몇 번째 자식인지 판별 }Node; int v, e, a,b, ancestor, subsize; int dist[MAX_N][2]; Node tree[MAX_N]; void init() { memset(dist, 0, sizeof(dist)); for (int i = 0; i < MAX_N; i..
행을 이동하면서 각 열에 퀸을 놔본다. #include #include using namespace std; int t,n; int col[11];// 각 행에 놓는 열의 위치를 저장한다 int cnt; bool check(int row) { for (int i = 0; i < row; i++) { if (col[i] == col[row] || abs(col[row] - col[i]) == row - i) {// 기울기가 판단 return false; } } return true; } void queen(int row) { if (row == n) {//모든 퀸 다 놓음 cnt += 1; return; } for (int j = 0; j < n; j++) {//놓을 열을 선택 col[row] = j; /..
높이를 깎아서 다른 높이를 전달할 수 있다 => 같은 위치더라도 다른 높이로 들어온다. 방문정보를 어떻게 전달할 지 몰라서 방문 처리가 어려워 dfs로 했다 package algo0424; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; int cut; intnum; int len; public Pos(int y, int x,int cut,int num,int len) { super(); this.y = y; this.x = x; this.cut=cut; this.num=num; this.len=len; } } public class S_1949_등산로조성_Solution { ..
a라는 사람과 b사람이 벌꿀을 채취하는데 벌집이 중복되지 않도록 해야된다. a라는 사람은 모든 행, 열 기준으로 고르는데 b라는 사람은 a와 같은 행이라면 열이 중복되지 않도록 해야하고 다른 행이면 상관없이 뽑는다. 1. collect 함수 a는 모든 경우를 전사적으로 구해주므로 list에 집어넣는다. (추후 다른 행이면서 열이 중복된 경우를 계산할 때 쓴다) b는 a와 행이 겹치지 않는 부분에서 subset을 돌려준다. 일단 이 함수에서 a의 최대값과 b의 최대값의 합의 최대값으로 answer를 갱신해주면 행은 같은 경우는 끝난다. 2. calculate함수 다른 행의 중복된 열을 구해준다. a라는 사람은 collect함수에서 전사적으로 모든 subset 경우를 구해줬다. a사람이 구한 리스트지만 이제..
처음에 플로이드 와샬로 풀었는데 t의 자리에 tc를 넣었다가 런타임에러 났었다. 내일 다시 플로이드 와샬로 풀어봐야지 내 위치에서 dfs로 돌면서 next(나보다 큰 친구들)의 count값을 증가시키면 next입장에서는 작은 애들의 개수만큼 업데이트가 된다. temp는 dfs를 도는 횟수를 가르키는데 현재 내 번호보다 큰 친구들의 수(나 포함)로 count[내번호]+temp 해주면 나보다 큰 친구들의 수를 구할 수 있다. 이렇게 temp로 업데이트 (나 포함해서 나보다 큰 친구들의 수) + count[next] 업데이트 (나보다 작은 친구수만큼 증가) 의 합이 n이 되면 나의 순서를 알 수 있는 경우이다. import java.util.ArrayList; import java.util.Scanner; p..
www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2번 감시카메라 방향 종류는 위아래 검사, 좌우 검사 2가지이고 5번 감시카메라는 1가지 이다. (사방을 검사하기 때문에) 나머지 감시카메라의 방향 종류는 4가지이다. (90도 회전할 때마다 검사하는 곳이 달라진다) 나는 위를 검사할 때를 0 , 오른쪽 1, 아래쪽 2, 왼쪽을 3으로 인덱스를 둬서 각각 해당방향으로 cctv가 닿는 곳을 검색하는 함수를 따로 구현했다. mark이차배열을 둬서 해당 위..
dfs로 백트래킹하면서 구해주는 완탐 문제였다 몇 번째 열을 골라서 A 혹은 B로 칠해줄 건지 구해야되는데 나는 vis[행 번호]에 칠해줄 알파벳을 써줬다. 고른 행이 1개 이상이면 k개 이상이 연속인지 확인하는 함수에서 해당 열만 바꿔준 숫자로 비교해줘서 통과하면 가장 작은 cnt개수로 갱신해줬다. import java.util.Scanner; public class Solution { static int t,d,w,k; static int[][] map; static int[] vis;// 뿌릴 약품 종류를 지정한다. a(1), b(2) static int answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in..
www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 물고기 이동은 구현에서 상어이동은 dfs로 완탐을 돌려줘야되는 문제여서 복잡했다 ㅠㅠ 지쳐.. 중간에 상어가 멈춰서 ?? 했는데 나는 상어이동을 bfs로 구현했고 물고기가 있는 칸으로만 이동하는 것으로 짰더니 빈 칸으로는 이동을 못해 오도가도 못한 상태로 끝나버렸다. 추후 빈 칸도 갈 수 있도록 했더니 통과되었다. 칸이 4x4로 정해져있기 때문에 무조건 3번 이동이 가능한지 for문으로 확인하..
www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 뒤에 1을 붙여주는 연산은 숫자 x*10+1 이라서 정수 범위 대략 2*10^9을 넘어가서 런타임에러가 난다. long형으로 바꿔줘야 된다. import java.util.Scanner; public class Main{ static long a,b; static long answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in); answer=-1; a=sc.nextInt(); b=sc.nextInt(); go(a,b,0); if(answer==..