그래프 : Graph (2)

정 승 연·2023년 1월 25일
BOJ1260
0

k0ding ㅌest

목록 보기
6/15

BOJ_1260

  • 초기에 정렬.

    단, 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문

    • 인접 리스트 경우, 초기에 정렬을 해놓아야 좋음
  • 구현
    static void dfs(int x){
	
	visit[x] = true;
	for(int y=1;y<=N;y++){
		if(visit[y]) continue;
		if(adj[x][y] == 0) continue;
		dfs(y);
	}
	
}
static void bfs(int start){
	Queue<Integer> que = new LinkedList<>();
	que.add(start);//!!
	visit[start] = true;
	while(!que.isEmpty()){
		int x = que.poll;
	
	for(int y=1;y<=N;y++){
			if(visit[y]) continue;
			if(adj[x][y] == 0) continue;
			que.add(y);
			visit[y] = true;
		}
	}
		
}
static void pro(){
	visited = new boolean[N+1];

}
static void input(){

BOJ_2667

인접한 영역로 단지를 이루어 단지 번호 붙이기

  • 정답의 최대치
    - 단지당 마을 수의 최대 : N^2 = 25^2 = 600
    - 단지 갯수의 최대 : (N^2) / 2 = 600 / 2 = 300
    • 격자형 그래프 구성 스크린샷 2022-10-20 오후 12.54.58.png
      • 각 격자를 그래프의 정점으로 인식.
      • 상하좌우로 인접해있는지에 따라 간선 연결
      • 새로운 단지의 start정점를 찾을 때마다 해당 단지에 속해있는 집들을 탐색을 통해 찾기
    • 구현
      static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};

static void dfs(int x, int y){
	// TODO : 단지에 속한 집의 개수 증가, visit 체크 하기
	group_cnt++;
	visit[x][y] = true;

	for(int k=0;k<4;k++){
			int nx = x + dir[k][0];
			int ny = y + dir[k][1];

			if(nx < 0 || ny < 0 || ny >= N || nx >= N) continue;
			if(a[nx].charAt(ny) == '0') continue;	
			if(visit[nx][ny]) continue;
	// TODO : 인접한 집으로 새로 방문하기
			dfs(nx,ny);

}

static void pro(){
	group = new ArrayList<>();
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(!visit[i][j] && a[i].charAt(j) == '1'){
					// 갈 수 있는데, 이미 방문 처리된(집이 있는), 즉 새롭게 만난 단지일 경우
					group_cnt = 0;
					dfs(i,j);
					group.add(group_cnt);
			}
		}
	}
		// TODO : 찾은 단지의 정보 출력
		Collections.sort(group);
		sb.append(group.size()).append('\n');
		for(int cnt:group) sb.append(cnt).append('\n');
		System.out.println(sb);
}

BOJ_2251

물을 옮겨 넣을 수 있을 때 C에 남아있는 물의 가능한 경우 (단, A는 비어 있어야 한다.)

  • 접근
    - A,B,C가 물통의 용량 , a,b,c를 각 물통의 현재 물의 양이라고 할 때
        → 하나의 (a,b,c) 로 표현 된다.
    
    - 0 ≤ a ≤ A ||  0 ≤ b ≤ B || 0 ≤ c ≤ C → 최대 200*200=8*10^6가지 상태 존재
- 물을 붓는 행위는? 상태가 바뀐다. 물을 붓는 행위가 상태를 변환시킨다.
    
    **→ 상태를 하나의 정점이라하고, 상태와 상태 사이의 변환(물을 붓는 행위)를 간선이라 하면 
        방향이 있는 가중치 그래프가 만들어진다.**
    • 탐색 시작
      • 주어진 초기 상태 (0,0,c)
    • 시간,공간 복잡도
      • 정점 : O(8*10^6)
      • 간선 : O(810^66) - 붓는 행위는 6번 가능
      • 시간 복잡도는 모두 O(8*10^6) → 1초 이내
    • 구현
      // 물통의 현재 상태와, 물을 붓는 행위를 관리하는 구조체
class State{
    int[] X;

    State(int[] _X){
        X = new int[3];
        for (int i = 0; i < 3; i++) X[i] = _X[i];
    }

    State move(int from, int to, int[] Limit) {
        int[] nX = new int[]{X[0], X[1], X[2]};

        if (X[from] + X[to] >= Limit[to]) {
            nX[from] -= Limit[to] - nX[to];
            nX[to] = Limit[to];
        }else{
            nX[to] = nX[from] + nX[to] ;
            nX[from] = 0;
        }
        return new State(nX);
    }
};
static void input(){
	Limit = new int[3];
	for(int i=0;i<3;i++) Limit[i] = sc.nextInt();
	visit = new boolean[205][205][205];
	possible = new boolean[205];
}

static void bfs(int x1,int x2,int x3){
	Queue<State> que = new LinkedList<>();
	
	visit[x1][x2][x3] = true;
	que.add(new State(new int[] {x1,x2,x3}));

	//BFS 시작
	while(!que.isEmpty()){
		State st = Q.poll();
		if(st.X[0] == 0) possible[st.X[2]] = true;
		for(int from=0;from<3;from++){
			for(int to=0;to<3;to++){
					if(from == to) continue;   //붓는 위치가 같은 수 없음
					State next = st.move(from,to,Limit);

					if(!visit[next.X[0]][next.X[1]][next.X[2]]]){
						visit[next.X[0]][next.X[1]][next.X[2]]] = true;
						que.add(next);
					}
				}
			}
		}
}

static void pro(){
	bfs(0,0,Limit[2]);

	// 정답 계산하기
	for(int i=0;i<=Limit[2];i++){
		if(possible[i]) sb.append(i).append(' ');
	}
	System.out.println(sb);
}

BOJ_2178

  • BFS 부가 효과를 이용한 최소 이동 횟수
    • 정답의 최대치
      • 밟게 되는 최대 개수 O(N^2)
    • BFS → 다른 정점까지 최소 이동 횟수도 계산 가능
      → 갈 수 있냐만 하는게 아니라 몇개 필요하냐까지 해주는 BFS
    • 구현
      static void bfs(int x, int y){
	// TODO : dist 배열 (갈 수 있으면 값, 없으면 -1) 초기화
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
				 dist[i][j] = -1;
		}
	}
	// TODO : (x,y)를 que에 넣어주고, visit 표시와 dist 값 초기화
	Queue<Integer> que = new LinkedList<>();
	que.add(x);
	que.add(y);
	dist[x][y] = 1;
	visit[x][y] = true;

	// BFS 과정 시작
	while(!que.isEmpty(){
		int x = que.poll();
		int y = que.poll();

		for(int k=0;k<4;k++){
			int nx = x + dir[k][0];
			int ny = y + dir[k][1];
			
			if(nx < 0 || ny < 0 || nx >=N || ny >= M) continue;
			if(a[nx].charAt(ny) == '0') continue;
			if(visit[nx][ny]) continue;

			que.add(nx);
			que.add(ny);
			visit[nx][ny] = true;
			dist[nx][ny] = dist[x][y] + 1; // 하나 더 밟아준다.

		}
	}
			
}
static void pro(){
	// TODO : 시작점이 (0,0)인 탐색 시작
	bfs(0,0);
	// TODO : (N-1,M-1)까지 필요한 최소 이동 횟수 출력
	System.out.println(dist[N-1][M-1]);
	
	

}

BOJ_1697

수빈이의 위치 N , 동생의 위치 K 이고,
수빈이가 1증가,1감소,내 위치 2배 증가 로 움직일 수 있을 때
수빈이가 동생을 찾을 가장 빠른 시간

  • 정답의 최대치
    N,K < 100,000 일때, ~~100,000^100,000 =~~ 

N > K라면, 1씩 감소하는 것 밖에 방법이 없다. 그럼 최대 10만초
    • graph만들기
      • 정점 : 수빈이가 가질 수 있는 상태, ‘점의 번호’가 곧 ‘정점의 번호’
      • 간선 : 이동을 의미하는 것, 각 점마다 +1,-1,*2를 향하는 “방향성 간선” → 최소 이동 간선 갯수
    • 구현
      static void bfs(){
	Queue<Integer> que = new LinkedList<>();
	// TODO : 수빈이의 위치 
	que.add(N);
	visit[N] = true;
	dist[N] = 0;
	
	// TODO : bfs 시작

	while(!que.isEmpty()){
		int x = que.poll();
		int y = x - 1; //여기를 바꿔가면서  dir{x-1,x+1,x*2} for 문으로
		if(0 <= y <= 10000 && !visit[y]){
			visit[y] = true;
			dist[y] = dist[x] + 1;
			que.add(y);
		}
}
static void pro(){
	bfs();
	System.out.println(dist[k]);
}

BOJ_3055

hi

BOJ_3055

난이도 4 ..
profile
정 승 연
이전 포스트

그래프 : Graph (1)

다음 포스트

트리 : Tree

0개의 댓글