알고리즘/DFS BSF

백준 - 13265 색칠하기

2024. 1. 25. 09:46
목차
  1. 문제
  2. 문제 풀이
  3. dfs

문제

https://www.acmicpc.net/problem/13265

 

13265번: 색칠하기

각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다.

www.acmicpc.net

그래프를 2가지 색으로 색칠하는 문제였는데, 서로 연결된 두 노드를 다른 색으로 칠할 수 있는지의 여부를 구하는 문제였다.

 

문제 풀이

그래프를 만들고 dfs로 모든 노드를 탐색하면서 색을 바꿔주면서 풀었다.

dfs

  • 현재 노드가 아직 색칠이 되지 않았으면 1로 색칠해준다.
  • 현재 노드와 연결된 노드들을 탐색한다
    • 다음 노드의 색이 없으면 방문 전이기 때문에 현재 노드 색과 다른 색으로 칠해주고 방문한다.
    • 다음 노드의 색이 있다면
      • 현재 노드의 색과 동일하면 impossible!
      • 현재 노드의 색과 다르고 방문 전이면 방문해준다.

모든 노드를 방문한 후에도 isPossible이 true라면 가능, flase면 불가능을 출력하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
using namespace std;
int N,M;
int color[1001] = {0}; //0: 색칠안됨 1: 색1 2: 색2
bool isPossible = true;
int visit[1001] = {0};
vector<vector<int>> G(1001);
int findNextColor(int nowColor){
if(nowColor == 1) return 2;
else return 1;
}
void dfs(int n){
if(color[n] == 0){ //아직 색칠 안됨 (맨 처음 노드)
color[n] = 1;
}
int nowColor = color[n];
int mustNextColor = findNextColor(nowColor);
visit[n] = 1;
for(int i=0;i<G[n].size();i++){
int nextNode = G[n][i];
int nextColor = color[nextNode];
if(nextColor == 0){ //방문x, 색칠하면 됨
color[nextNode] = mustNextColor;
dfs(nextNode);
}
else{
if(nowColor == nextColor){ //불가능
isPossible = false;
return;
}
else { //가능, 방문 안했으면 dfs
if(visit[nextNode] == 0) dfs(nextNode);
}
}
}
}
int main(int argc, char** argv)
{
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d",&N,&M);
fill(&G[0], &G[1001], vector<int>(0));
fill(color, color+1001, 0);
fill(visit, visit+1001, 0);
isPossible = true;
for(int i=0;i<M;i++){
int a,b;
scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int i=1;i<=N;i++){
if(visit[i] == 0) dfs(i);
if(!isPossible) break;
}
if(isPossible) printf("possible\n");
else printf("impossible\n");
}
return 0;
}
  1. 문제
  2. 문제 풀이
  3. dfs
'알고리즘/DFS BSF' 카테고리의 다른 글
  • 백준 - 16637 괄호 추가하기
  • 백준 - 23747 와드
  • 프로그래머스 - 도넛과 막대 그래프
  • 백준 - 17070 파이프 옮기기 1
hahihi
hahihi
히호 노트hahihi 님의 블로그입니다.
hahihi
히호 노트
hahihi
전체
오늘
어제
  • 분류 전체보기 (224)
    • 알고리즘 (114)
      • 정렬 (3)
      • 그리디 (9)
      • 구현 (35)
      • 이분 탐색 (4)
      • 탐색 (2)
      • 동적 계획법 (DP) (11)
      • DFS BSF (29)
      • 최단 경로 (5)
      • 그래프 (4)
      • 주의할 점 (4)
      • 트리 (3)
    • spring (34)
      • JPA (12)
    • DevOps (10)
      • Docker (3)
    • java (15)
      • 이펙티브자바 (4)
      • Clean Code (4)
    • git (9)
    • DB (3)
    • 앱개발 (1)
    • 유닉스 (26)
    • 네트워크 (3)
      • IT 엔지니어를 위한 네트워크 입문 (3)
    • 유니티 (1)
    • 후기 (4)
    • 누누코코 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 입출력
  • 13265
  • 숫자 조각
  • dp
  • 팀 결성
  • JWT
  • spring
  • BaseEntity
  • Docker
  • 공통 response
  • 1868
  • 4193
  • 이코테
  • 백준
  • allowPublicKeyRetrieval
  • 도넛과 막대 그래프
  • 프로그래머스
  • SWEA
  • 그리디 알고리즘
  • 7465

최근 댓글

최근 글

hELLO · Designed By 정상우.
hahihi
백준 - 13265 색칠하기
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.