판교의 메타몽

문제 링크 The problem link : LeetCode 1971. Find if Path Exists in Graph 문제 요약 노드의 개수 n, 간선들이 연결되어있는지 알려주는 배열 edges, 출발지 source, 목적지 destination이 주어집니다. 해당 그래프에서 source와 destination이 연결되어있는지 확인하고, 연결되어있을 경우 true를 반환하세요. Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 Output: true Explanation: There are two paths from vertex 0 to vertex 2: - 0 → 1 → 2 - 0 → 2 문제 풀이 class Soluti..

문제 링크 : https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이 문제는 다음과 같은 방법으로 접근할 경우 시간초과를 겪게된다. 배열의 값이 1인 경우, 해당 위치를 기준으로 4방위의 값이 0인 곳에서 DFS / BFS를 진행해 이동할 수 있는 칸의 갯수를 센다. 시간 제한은 2초인데, 1000*1000배열을 하나하나 BFS / DFS로 파고들었다가는 시간초과가 날 수 밖에 없다. 때문에 이 문제는 좀더 거시적인 관점에서 ..

문제 링크 : https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net 이 문제에서 핵심 요소는 이미 거쳐갔었던 돌의 갯수들을 어떻게 skip하느냐이다. 즉, 방문했던 곳은 재방문하지 않는다는 BFS와 DFS의 기본 사항을 어떻게 지키느냐가 관건인데, 나는 다음과 같은 방법을 사용했다. 돌 그룹 3개중 갯수를 바꿀 수 있는 그룹은 2개 뿐이다. 때문에 2개의 돌 그룹의 갯수들을 문제의 요구대로 먼저 갯수를 변경해준 뒤, 만약 변경된 갯수들이 이미 거..

문제 링크 : www.acmicpc.net/problem/1696416964번: DFS 스페셜 저지첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루www.acmicpc.net이 문제는 백준 16940번 BFS 스페셜 저지 - 2에서 활용한 기법으로 풀 수 있다.백준 16940번 BFS 스페셜 저지 (C++) - 2문제 링크 : www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 이 문제를 이전에 풀었을 때, 머릿..

문제 링크 : www.acmicpc.net/problem/1294612946번: 육각 보드크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다. 육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다. 어떤 칸www.acmicpc.net이 문제에서 먼저 유의해야할 점은 다음과 같다. 1. 육각보드다.주변의 X자를 판별할때 위치값을 잘 선정해야한다. 무턱대고 사각형이나 정사각형으로 생각하다가는 곧 바로 틀려버린다. 2. 색칠하는 갯수의 최대값은 3밖에 나올 수 없다. 위의 그림에서 X로 표시된 구역을 제외하고 나머지 영역에 색을 칠한다고 가정하자.색을 넣을때 R는 붉은색, B는 푸른색, P는 보라색으로 가정한다면 위..

문제 링크 : www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 이 문제의 관건은 다음과 같다. 위 이미지에 표시된 치즈 내부에 있는 구멍과 외부 공기를 구분하는 것이다. 문제 풀이는 다음과 같다. 1. 먼저 아래코드는 공기와 접촉된 모든 치즈들을 녹이는 코드이다. 대략적으로 훑어보고 다음 차례에서 세세한 설명을 이해해보자. while(true){ done = false; cheese = 0; outofcheese(1,1); // 치즈 밖의 공기들만 별도로 표시해주는 ..

문제 링크 : www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제 풀이는 다음과 같다. 1. 2차원 배열을 입력받는다. 2. 배열의 첫 지점부터 끝지점까지 2중 for문을 돌린다. 만약 해당 지점을 방문한 적이 없으면 dfs를 시작한다. dfs로 넘겨받는 인자는 다음 세개이다. (1) x좌표 (2) y좌표 (3) 지금까지 거쳐온 지점의 갯수 또한 이때 주의해야할 점이 있다. for(int i=0; i

문제 링크 : www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 문제 풀이는 다음과 같다. (1) 전형적인 DFS문제로, A팀과 B팀으로 나뉘는 조합을 DFS로 구한다. (1)-(2) 즉, bool문을 만들어 1번과 2번이 같은 팀이면 두 번호를 true로, 3번과 4번이 같은 팀이면 자동적으로 남은 사람들은 false로 구성해준다. (2) 그렇게 true끼리 묶인 사람끼리의 합과 false끼리 묶인 사람들의 합의 ..

문제 링크 : www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 이 문제에서 주의해야할 점이 있다. (1) 우유를 많이 먹고 끝내는게 아니라, 우유를 많이 먹고 집으로 되돌아와야 한다. (2) 출발지와 목적지가 정해져있다. 문제를 대충 읽은 탓에 집으로 되돌아오는 조건을 빼먹었고, 결국 두어차례 오답을 겪게되었다. 또한 (2)번 역시 매우 중요한 포인트인데, 출발지점과 목적지점이 뚜렷하며 동시에 중도 포기 조건 (return) 또한 명시되어..

문제 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 설명은 단순했지만 생각만큼 쉽게 풀리지 않았던 문제이다. 첫 도전의 실패는 다음과 같다. (1) 최초에는 이분 검색으로 접근을 시도했다. 하지만 예외 케이스(특히 32888의 케이스)가 쉽게 풀리지않아, 점차 코드에 예외처리가 덕지덕지 붙는게 보였고, 이분 검색은 원하는 방법이 아님을 깨달았다. (2) 그러다가 Discussion 창에서 DFS, BFS로 풀릴 수 있다는 의견을 접해 DFS로 풀었다. (3) DFS로 푸는것 까지는 좋았지만 예외케이스에 대한 처리는 필수적이었다 (특히 4321의 케이스) 문제 풀이는 다음과 같다. (1) 문자열을 숫자로 ..