https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 나는 처음에 이 문제에서 주어진 이분 그래프가 뭔지 잘 이해하지 못했다. 그래서 구글링을 통해 위키백과에 정의 된 그림도 봐보고 다른 사람들의 설명도 봐보았다. 문제에 주어진 아래와 같은 설명은 나같은 감자에게는 이해하기 어렵다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Gr..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 오늘 풀어본 문제는 여지껏 해왔던 BFS문제와는 조금 다르다. 다른 문제들과 다른점이 무엇인가 하면 방문처리의 배열이 다르다. 지금까지는 1차원 또는 2차원 배열로 방문처리를 해왔다. 하지만 이 문제는 3차원 배열로 처리해야한다.(물론 토마토 문제의 경우 3차원이 있었다. 하지만 이 문제의 3차원 배열은 좀 다르다.) 문제의 내용은 벽을 딱 한번 부술 수 있고, (1,1)..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제는 1에서 시작해서 100에 도달하는 방법을 주사위가 나오는 눈의 수로 했을 때 최단으로 가는 걸 구하는 문제다. 여기서 신경 쓸것은 뱀과 사다리이다. 기본적으로는 주사위의 눈의 수만큼 이동하지만 사다리나 뱀을 만나면 그 위치로 이동하게 된다. 처음 이 문제를 풀때 헷갈리는 부분이 있었다. 시작점을 1로하고 수를 셀 때, 뱀이나 사다리에 도달하..
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 이번 문제는 knight의 이동 문제이다. 말그대로 체크판에서 하나의 시작점에서 도착지점으로 이동하는 최소 횟수를 구하는 것이다. 즉, 나이트가 이동하는 방향은 8방향이 있다. 그림으로 나타내면 문제의 주어진 아래의 그림과 같다. 그리고 이걸 x,y 좌표로 나타내면 아래와 같이 나타낼 수 있다. int[] dx = {1, 2, 2, 1,-1,-2,-2,-1}; int[] dy = {2, 1,-1,-..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 2667번과 거의 동일하다. 다른 점이라면 테스트 케이스를 입력 받은만큼 실행한다는 것과, 배추가 있는 좌표를 찍어야 한다는 점 정도이다. 나머지는 2667번과 동일하게 DFS,BFS 모두로 풀 수 있을 것이다. 풀이 방법은 먼저 테스트 케이스를 몇 개 실행할지 입력 받는다. 그 다음에 가로 길이 M과 세로 길이 N을 입력 받고 배추의 갯수인 K를 입력받는다. 그 다음 아래 K개의 줄에 배추가 있는..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이 문제는 조금 헷갈리는 부분이 있었다. 1인 부분에 대해서 탐색을 모두 해야하는데 그걸 어떤식으로 해서 반복해야하는지 막막한 부분이 있었는데, 질문 게시판에서 그에 대한 해결책을 얻었다. 방법은 주어진 단지 테이블에서 각각의 위치마다 1인것에 대해 DFS나 BFS를 통해 탐색을 진행하는 방식으로 하면 된다는 것을 알았다. 즉, 단지 테이블에 1인 지점이 나오면 이에 대해 탐색을 진행하고, 탐색이 ..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이번에는 BFS와 DFS 중에 선택하여 푸는 문제를 풀어보았다. 나는 우선 BFS에 대해 공부하기 위해서 BFS로 풀었다. 그리고 문제를 생각했을 때 DFS보다는 BFS가 접합하다고 생각했다. 왜냐하면 시작 노드와 근접한 모든 노드를 찾는 것이기 때문에 DFS로 하나의 노드에 대해서 계속 찾아갔다가 돌아오는 방식은 오래걸릴 것 같아서이다. 또한 잘못하여 노드의 깊이가 너무 깊을 경우 시간 초과가 발생할..
https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 저번에 이어서 DFS기초 문제를 다시 풀어보았다. 저번과 같은 코드이지만 내림차순이어서 인접 리스트의 정렬을 내림차순으로 바꿔주기만 하면 된다. 너무 간단한 문제여서 오늘은 짧게 설명하겠다. 방문 여부를 판단하는 boolean배열과 순서를 담을 int배열 그리고 순서값을 셀 count 그리고 node의 갯수가 있으면, boo..
