밤이 블로그

BOJ#1613 역사 * 문제https://www.acmicpc.net/problem/1613 * 풀이플로이드 와셜 알고리즘에 따라 Start -> 임의의 노드 -> End를 만족하는 임의의 노드가 존재할 때 (자기 자신을 포함하여) Start -> End 를 만족함을 알 수 있습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/644019c1ecb2b486c6597f4c2570edae8f97760f/BOJ%231613/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer..

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 * 문제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#1525 퍼즐 * 문제https://www.acmicpc.net/problem/1525 * 풀이종만북을 참고하여 풀었습니다.To-Do : bfs, 양방향탐색, dfs 방법으로 각각 풀어보기 저는 이번에 bfs와 비트마스크를 이용해보았습니다. 맵은 하나의 정점으로 볼 수 있습니다. (총 정점의 수는 9! : 1부터 9까지 순서대로 나열하는 경우의 수와 같다) 그리고 상하좌우 4방향으로 이동할 수 있으니, 한 정점에서 최대 4개의 정점과 연결될 수 있습니다.즉, 주어진 정점에서 시작하여 4방향 탐색을 해나가면서 목표를 찾으면 되겠습니다. 문제는 어떻게 중복 방문을 체크하고 처리할 것인지 생각해봐야 합니다.저는 비트마스크를 이용해보았습니다. 각 값은 0부터 8사이의 값이므로, 각 값은 4비트를 사용하면..

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

BOJ#1600 말이 되고픈 원숭이 * 문제https://www.acmicpc.net/problem/1600 * 풀이bfs 탐색 문제입니다.일반적인 격자(상,하,좌,우) 문제에서 말처럼 이동하는 부분이 추가되었다고 생각하면 됩니다. 즉, 각 위치에서 상하좌우(4방향) + 말(8방향) 이렇게 12가지 방향으로 탐색을 진행하면 됩니다.문제는 중복된 정점을 다시 방문하지 않도록 처리하는 것입니다. 처음에 제가 실수했던 점은 discovered[row][col][말로 방문한 경우 or 원숭이로 방문한 경우] 로 중복된 정점을 처리했었는데 이것의 반례로 아래의 예가 있습니다. 15 50 1 1 0 10 0 1 0 10 0 0 1 10 1 0 1 01 1 0 1 0 정답 : 6 말의 움직임에 의해 (2,1)에 위치..

BOJ#2931 가스관 * 문제https://www.acmicpc.net/problem/2931 * 풀이이 문제는 어려운 문제인지, 쉬운 문제인지 헷갈리네요. - 삭제된 노드는 단 1개이고 쉽게 찾을 수 있다. (출발점에서 파이프를 따라가보면 삭제된 노드가 나온다)- 위치는 구했고 거기에 맞는 파이프만 찾으면 되는데 노드에서 출입구가 몇개이고 어느 방향으로 뚫려있는지만 알면? 파이프를 구할 수 있다. 쉽다고 생각하면 쉬운데,,,정형화된(?) bfs, dfs 탐색으로는 어떻게 풀까? 문제 의도는 뭘까 아무튼 bfs, dfs 몰라도 자기 생각을 코드로 옮길 수 있으면 이 문제는 쉽게 풀 수 있을 것 같습니다.입사 시험에 적당한 문제 ↓ 테스트 케이스 보기 (클릭) ↓4 4Z...|...|....--M 4 1..

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#10875 뱀 * 문제https://www.acmicpc.net/problem/10875 * 풀이 ※ 문제 풀 때 주의할 점 주어진 입력의 크기를 잘 살펴봅시다. L 7 TestCase #2332 L4 L4 R => 6 TestCase #3332 R1 R10 R = 9 TestCase #4332 R10 L4 R = 6 TestCase #5332 L10 L4 R = 6 TestCase #63310 L4 L4 R = 4 TestCase #7332 L4 L4 R = 6 TestCase #8342 L2 L1 L5 R = 7 TestCase #9342 R2 R1 R5 L = 7 TestCase #10352 R3 L1 L2 L10 L = 9 TestCase #11352 R3 R1 R2 R10 L = 9 Te..