본문 바로가기
반응형

dfs10

프로그래머스 - 삼총사 / C++ 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/131705 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 원소 중 3개를 택해 합이 0이 되는지 확인하면 되는 문제. 브루트포스와 DFS 두 가지 방법으로 풀어보았다. 브루트포스 코드 #include using namespace std; int solution(vector number) { int answer = 0; for(int i=0; i 2022. 12. 24.
BOJ 14502 - 연구소 / C++ 문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 벽 3개를 세울 수 있는 경우의 수는 DFS로 완전탐색하고 그렇게 생성된 배열을 다시 BFS로 순회하며 바이러스를 퍼뜨리고 안전 영역을 세야한다. 우선, 입력 받은 배열을 돌며 0(빈 칸)을 발견하면 해당 지역부터 DFS를 시작한다. 해당 지역에 벽(1)을 세우고 DFS 카운트를 늘려준 뒤 다시 배열을 돌며 다음 0(빈 칸)을 찾는다. 이렇게 DFS의 카운트가 3이 되면 벽을 모두 세웠으므.. 2022. 5. 4.
BOJ 14500 - 테트로미노 / C++ 문제 링크 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 보라색 모양 블록(ㅗ, ㅜ, ㅏ, ㅓ)를 제외하고는 모두 DFS로 순회할 수 있다. 따라서, DFS로 순회하며 Depth가 0부터 시작하여 3일 때 멈추고 answer값을 최댓값으로 갱신해준다. 보라색 모양의 블록은 4가지 경우를 모두 직접 구현해야한다. 단순 좌표 계산만 하면 되므로 그렇게 어렵지 않다. 모든 좌표를 돌며 answer값을 최댓값으로 갱신하고 출력해주면 된다. .. 2022. 5. 2.
프로그래머스 - 거리두기 확인하기 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 풀이 배열을 순회하다 사람('P')이 있다면 DFS를 수행한다. DFS의 종.. 2022. 4. 28.
반응형

티스토리툴바