밤이 블로그

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#3190 뱀 * 문제https://www.acmicpc.net/problem/3190 * 풀이map과 direction 2차원 배열을 선언하였습니다. map이 가질 수 있는 값 : 0(빈칸), 1(뱀), 2(사과) direction이 가질 수 있는 값 : 상, 하, 좌, 우→ 각 위치(row, col)에서 머리 또는 꼬리가 어느 방향으로 이동해야 하는지 알기 위함 시뮬레이션 진행 알고리즘은 아래와 같고, 중간 중간에 map과 direction 정보를 업데이트해서 답을 찾을 수 있게 하였습니다. 머리 이동 - 맵을 벗어난 경우 - 종료 - 빈칸인 경우 - 꼬리 이동 - 사과인 경우 - None - 뱀인 경우 - 종료 ↓ 테스트 케이스 보기 (클릭) ↓5054 D8 D12 D15 D20 L 20 83..

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..

BOJ#13911 집 구하기 * 문제https://www.acmicpc.net/problem/13911 University > 서강대학교 > 제 12회 총장배 서강대학교 프로그래밍 대회 Master F번 * 풀이매우 매우 추천하는 문제입니다. - 처음 생각한 알고리즘 1. 맥도날드 지점별로 다익스트라2. 스타벅스 지점별로 다익스트라3. 조건 만족하는 것 찾아내기 문제를 본격적으로 풀어보려는데,, 뭔가 찜찜합니다.입력값 범위가 심상치 않아 문제를 풀기전에 시간복잡도를 계산해봅니다. V ≤ 10,000, E ≤ 300,000 맥도날드 다익스트라 (V-2)번 : O(E*log(V)) * V-2번스타벅스 다익스트라 (V-2)번 : O(E*log(V)) * V-2번조건 만족하는 것 찾아내기 : ?? 결론 : 시간..

BOJ#1938 통나무 옮기기 * 문제https://www.acmicpc.net/problem/1938 * 풀이통나무의 길이가 항상 3이므로, 중심 위치만을 가지고 탐색을 해봅시다.상하좌우, 회전 5가지 경우의 bfs 탐색을 진행하면 되겠습니다. 정점 중복 방문 처리는 discovered[행][열][통나무 방향(세로 또는 가로)]으로 잡아봤습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/ca62ee46326ab3ef50a46f562b4783773e0e0551/BOJ%231938_MovingLogs/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

BOJ#2665 미로 만들기 * 문제https://www.acmicpc.net/problem/2665Olympiad > 한국정보올림피아드 > KOI 1997 > 고등부 2번 * 풀이쉬운 문제입니다. 20년 묵은 문제네요, 😅 왜 쉽냐면,검은 방을 흰색 방으로 바꾸는 개수의 제한도 없고, 바꿀 때 필요한 규칙도 없기 때문입니다. 그냥 이 문제는.. 다익스트라 돌리면 됩니다. 비슷한 문제 : 1261번 - 알고스팟 https://www.acmicpc.net/problem/12612206번 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 * 나의 코드 https://github.com/stack07142/BOJ/blob/431a2fe10059904f604d38bc137..

BOJ#1194 달이 차오른다, 가자. * 문제https://www.acmicpc.net/problem/1194 * 풀이bfs 탐색 문제입니다.같은 정점을 여러번 방문해야 하는데, 어떻게 방문 여부를 처리할 것인가를 생각해야 합니다. (처리하지 않으면 큐 폭발) 저는 아래와 같이 discovered 배열을 boolean[row][col][열쇠]로 구성하였습니다. 즉, 해당 위치 (row, col)에 동일한 key를 갖고 방문한 적이 있으면 다시 방문할 필요가 없다는 것입니다. key는 a부터 f까지 6개가 있으므로 비트마스크를 이용하면 6bit로 가지고 갖고 있는 key의 정보를 표현할 수 있습니다.(배열 사이즈는 여유있게 설정했습니다.) static boolean[][][] discovered = ne..