본문 바로가기
반응형

코딩테스트 준비/백준 C#167

백준 C# - 7576 +) 풀이 문제에 최소가 들어가면 BFS와 관련된 확률이 높다. 들어가기 앞서 주의! 01 그래프 (0,0)부터 입력받기 DFS, BFS문제에서 음수가 되는 경우를 배제하기 위해서 그래프값을 (1,1)을 넣으면서 진행하였는데 여기서는 그렇게 하면 안된다. 원인이 이거인지 모르고 열심히 그리다가 시간을 많이 소모하였다.. 하ㅏㅎㅏ.. 앞으로 (0,0)에 넣고 조건문을 넣어 푸는게 좋을 것 같다는 생각이 들었다. 02 string에 어떤 값이 들어가는지 꼭 확인하기 string문을 입력받으면 띄어쓰기 까지 입력이 받아진다. string s = Console.ReadLine() 그래서 Replace를 사용해서 띄어쓰기를 삭제했다. string s = Console.ReadLine().Replace(" ",""); 그랬더.. 2023. 12. 19.
백준 C# - 4963 +) 풀이 우리가 앞서 풀었던 문제는 상하좌우만 움직이는 문제이다. 하지만 이번 문제는 대각선까지 움직이는 것이 추가되었다. 이부분만 다르지 나머지 부분은 똑같다. 나머지 부분에 대한 설명은 아래 문제 참조 백준 C# - 2667 +) 풀이 이 문제를 풀기 앞서 아래 문제를 풀고 오는 것을 추천한다. 2667이 아래 문제의 심화버전이다. 백준 C# - 1012 백준 C# - 1012 +) 풀이 먼저 문제 이해부터 해보자 문제에서 배추 흰지렁이가 한 배추의 code-piggy.tistory.com 대각선 + 상하좌우 움직이는 방법 대각선과 상하좌우로 움직이는 경우의수를 구하면 아래와 같이 9가지가 나온다. 01 상하좌우 코드 상하좌우를 확인하면서 구하는 코드는 아래와 같이 구했었다. static int[] dirX .. 2023. 12. 18.
백준 C# - 2178 +) 풀이 최단거리 문제는 BFS를 사용하는 것이 좋다. 101111 101010 101011 111011 먼저 BFS의 최단 경로 과정을 보면 아래와 같이 진행된다. 해당 깊이에 갈 수 있는 주변 칸을 탐색하고 다음 깊이로 넘어가는 것을 확인할 수 있다. BFS가 진행됨에 따라 칸의 값 갱신 BFS를 진행하면서 현재 칸을 방문할때 이전의 방문했던 칸에 1을 더한 값을 현재 셀에 저장하여 몇 번째 방문한 것인지 를 저장하면 마지막 칸에 최단 경로가 저장된다. graph[newX, newY] = graph[now.Item1, now.Item2] + 1; BFS 알고리즘 짜기 01 큐 초기화 및 시작 지점 추가하기 Queue queue = new Queue(); // 시작 좌표값 queue에 추가 queue.Enque.. 2023. 12. 16.
백준 C# - 2667 +) 풀이 이 문제를 풀기 앞서 아래 문제를 풀고 오는 것을 추천한다. 2667이 아래 문제의 심화버전이다. 백준 C# - 1012 백준 C# - 1012 +) 풀이 먼저 문제 이해부터 해보자 문제에서 배추 흰지렁이가 한 배추의 상하좌우로 다른 배추로 이동할 수 있다고 나와있다. 1) DFS를 이용해서 상하좌우로 이동할 수 있을때까지 이동하면서 확인해야 code-piggy.tistory.com 백준 C# - 1012를 풀었다는 전제하에 문제 풀이를 진행하겠다. 출력에 필요한 두 부분 01 총 그룹의 갯수 출력(1012 : 지렁이의 갯수) 이 부분은 원래 1012와 동일하게 출력하면 된다. 02 단지내 집의 수 오름차순으로 출력(1012 : 각 지렁이에 해당되는 배추들의 수) 각 단지내 집의 수는 DFS가 호출되는 .. 2023. 12. 14.
백준 C# - 1012 +) 풀이 먼저 문제 이해부터 해보자 문제에서 배추 흰지렁이가 한 배추의 상하좌우로 다른 배추로 이동할 수 있다고 나와있다. 1) DFS를 이용해서 상하좌우로 이동할 수 있을때까지 이동하면서 확인해야 한다. 2) 그 그룹의 끝에 다다랐으면 다음으로 배추가 심어진 곳을 찾아 배추가 심어진 곳이 없을때까지 이를 반복하면 된다. 상하좌우 탐색에서 -값이 나오는 경우를 먼저 살펴보자 1 5 3 6 0 2 1 2 2 2 3 2 4 2 4 0 문제를 표로 나타내면 아래와 이미지와 같다. 상하좌우 탐색 static int[] dirX = { 1, -1, 0, 0 }; static int[] dirY = { 0, 0, 1, -1 }; 만약 x가 0이고 y가 4인 경우 for (int i = 0; i < 4; i++) { int .. 2023. 12. 14.
백준 C# - 1707 +) 풀이 이분 그래프 그래프의 모든 정점을 서로 다른 두가지 색으로 칠할 수 있는 그래프이다. 그래프의 정점을 두 그룹으로 나누었을때 같은 그룹에 속한 정점들 간에는 간선으로 연괼되어 있지 않고 서로 다른 그룹에 속한 정점들 간에만 간선으로 연결되어 있다. 이분 그래프 알고리즘 주로 DFS나 BFS를 이용해서 구현한다. 01 그래프의 시작 정점을 색을 칠한다. 02 다음 정점은 현재 정점과 다른 색으로 칠한다. 03 만약 이미 색이 칠해져 있는데 현재 정점과 인접한 정점의 색이 같다면 이는 이분 그래프가 아니다. 문제를 풀어보자 DFS을 이용하자 static void DFS(int now, int group) { visited[now] = group; foreach(int next in graph[now]) { .. 2023. 12. 10.
반응형

티스토리툴바