본문 바로가기

dfs4

백준 9466번 C++ 텀 프로젝트 텀 프로젝트https://www.acmicpc.net/problem/9466이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.예를 들.. 2019. 6. 15.
백준 1012번 C++ 유기농 배추 유기농 배추https://www.acmicpc.net/problem/1012차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 .. 2019. 6. 12.
백준 4963번 C++ 섬의 개수 섬의 개수https://www.acmicpc.net/problem/4963정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 푸는 법DFS 혹은 완전 탐색으로 풀면 된다고 한다.(i, j)의 위치에서 인접해있는 8개의 위치를 조사해서 탐색해나가면 되는 문제다.map[i][j]이 0이 아니라면 map[i][j]에 0을 대입하고 주변을 탐색한다.map[i][j]=0은 이미 방문한 섬이므로 중복을 방지하기.. 2019. 6. 12.
백준 1707번 C++ 이분 그래프 이분 그래프https://www.acmicpc.net/problem/1707그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 푸는 법이분 그래프인지 확인하는 법알고리즘 검색하다 보면 꼭 나오는 이 분의 블로그를 보고 그냥 이대로만 하면 맞을 수 있다.주의할 점은 테스트 케이스를 실행할 때마다 그래프와 체크를 초기화해주는 것이다.나는 DFS로 풀었고, 만약 start의 색깔과 next의 색깔이 이미 존재하고(둘다 방문했고) 색깔이 같으면 재귀문을 빠져나와 answer이 N.. 2019. 6. 12.