DFS 13

BOJ#10972 다음 순열

BOJ#10972 다음 순열 * 문제https://www.acmicpc.net/problem/10972 * 풀이 순열 설명http://stack07142.tistory.com/24 순열 설명(사전순)http://stack07142.tistory.com/155 쉬운 것 같으면서도 어려운 문제였습니다.문제 해결 알고리즘은 다음과 같습니다. 위 순열 설명 링크와 순열 설명(사전순) 링크를 다 읽으셨다는 가정 하에 설명해보겠습니다. , A = [1, 3, 4, 2] 주어진 순열의 끝을 idx로 지정하고, A[idx-1] 0 && A[idx - 1] > A[idx]) idx--; idx는 2가 되고 아래와 같이 두..

BOJ#1890 점프

BOJ#1890 점프 * 문제https://www.acmicpc.net/problem/1890 * 풀이dp + dfs로 풀었습니다.정답 비율에 비해 문제가 굉장히 쉽습니다. N 범위와 경로의 개수 범위(long)만 주의하면 될 것 같습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231890/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static final int[] dRow = {0, 1}; stat..

BOJ#10429 QUENTO

BOJ#10429 QUENTO * 문제https://www.acmicpc.net/problem/10429 * 풀이 dfs 탐색으로 풀었습니다. 개인적으로 문제가 너무 재미있었습니다. 어렵지 않아서 풀이는 생략. * 나의 코드https://github.com/stack07142/BOJ/blob/646def24b7052ba5f4f933c5bfbc7fa9c1b65ce3/BOJ%2310429_QUENTO/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * 선데이코딩 베타라운드1 - D. 수학 퍼즐 게임 * BOJ#10429 QUENTO * https://www.acmicpc.net/problem/10429 */ public class ..

BOJ#14502 연구소

BOJ#14502 연구소 * 문제https://www.acmicpc.net/problem/14502 * 풀이2017년 상반기 삼성 SW 역량평가 기출문제 입니다. 벽을 항상 3개 설치해서 안전영역의 최대값을 구해야 하는 문제입니다.즉, 완전 탐색이 필요합니다. (모든 경우를 다 해봐야 최대값을 구할 수 있음) 저는 아래와 같이 풀어보았습니다. 1. 조합을 돌려서 Map에서 빈칸 3개를 선택한 후 벽으로 바꿔줍니다. 최대 8*8 맵에서 빈칸 3개를 선택할 때 경우의 수 = (64-2)C3(바이러스가 최소 2개 있으므로) 2. 해당 Map에서 바이러스를 퍼뜨립니다. 3. (맵의 크기 - 바이러스의 수 - 벽의 수) 의 최대값을 갱신합니다. 4. 1~3 반복 * 나의 코드 https://github.com/s..

BOJ#14500 테트로미노

BOJ#14500 테트로미노 * 문제https://www.acmicpc.net/problem/14500 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출 문제입니다. 테트로미노에서 dfs로 탐색 가능한 블록이 있고, 탐색 불가능한 블록(ㅓ, ㅗ, ㅜ, ㅏ)이 있습니다.즉, dfs로 탐색 + (ㅓ,ㅗ,ㅜ,ㅏ)에 대해 탐색을 하면 답을 얻을 수 있습니다. (ㅓ,ㅗ,ㅜ,ㅏ) 탐색 아이디어는 다음과 같습니다. 현재 위치가 (row, col)일 때(row, col)값과 (row, col)에서 상,하,좌,우 4방향 값을 모두 더해줍니다. 그리고 4방향 값에서 최소 값을 다시 빼줍니다.= 현재 위치 값 + 4방향 sum - 4방향 값 중 최소값 즉 플러스 + 모양에서 4방향 중 가장 최소값을 빼면 (ㅓ,ㅗ,ㅜ,..

BOJ#2638 치즈

BOJ#2638 치즈 * 문제https://www.acmicpc.net/problem/2638 * 풀이가장자리에는 친절하게도 치즈가 존재하지 않으므로가장자리에서 dfs 탐색을 하면 외부 공기 지역을 구별해낼 수 있습니다. 1. 외부 공기 탐색(dfs)2. 모든 치즈에 대해 외부 공기 접촉 판단3. 접촉 시 치즈 없애기4. 1~3 반복....(치즈가 모두 없어질때까지) 주의할 점으로는...치즈를 즉시 외부 공기로 바꾸면 주변 치즈에 영향을 주게 되어 정확한 답을 구할 수 없습니다. 개선할 점으로는...step마다 dfs 탐색을 한번씩 수행하는 부분을 없앨 수 있겠습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/c6b101df6246e4a5c45c00a905ca92..

BOJ#2667 단지번호붙이기

BOJ#2667 단지번호붙이기 * 문제https://www.acmicpc.net/problem/2667 * 풀이dfs난이도 : 하 추천 문제 (2667번 다음에 풀어보면 좋을 문제) : 2146번 - 다리 만들기 https://www.acmicpc.net/problem/2146 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232667_Numbering/src/Main.java import java.io.*; import java.util.ArrayList; import java.util.Collections; /** * BOJ#2667 단지번호붙이기 * https://www.acmicpc.net/problem/2667 */ public class..

BOJ#2146 다리 만들기

BOJ#2146 다리 만들기 * 문제https://www.acmicpc.net/problem/2146 * 풀이1. dfs 섬 구분하기2. bfs 섬 간 최단 거리 구하기 문제 추천 (2146번을 풀기전에 보면 좋을 문제) :2667번 - 단지번호 붙이기 https://www.acmicpc.net/problem/2667(섬 개수를 세는 문제)* 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%232146_MakeBridge/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /** *..

BOJ#1182 부분집합의 합

BOJ#1182 부분집합의 합 * 문제https://www.acmicpc.net/problem/1182 * 풀이처음에는 조합을 이용해서 풀었습니다. (160ms)집합에서 1개를 고르는 경우, 2개를 고르는 경우, ...., N개를 고르는 경우 두번째 풀때는 집합의 각 원소의 2가지 경우에 대해(고르는 경우, 고르지 않는 경우)재귀 함수 호출로 답을 구하였습니다. (76ms) 주의할 점 : S가 0인 경우에는 공집합도 카운트 될 수 있음 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231182_SumOfSubsets/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BO..

BOJ#12101 1, 2, 3 더하기 2

BOJ#12101 1, 2, 3 더하기 2 * 문제https://www.acmicpc.net/problem/12101 * 풀이dfs로 풀었습니다. dfs를 돌리면 자연스럽게 오름차순으로 결과가 나옵니다.풀이는 쉽기 때문에 생략합니다. dp로 다시 푼 후 업데이트 예정. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2312101_Sum123_2/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#12101 1, 2, 3 더하기 2 * ..

Algorithm/DP 2017.04.06