https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 이번 문제는 순열 사이클의 갯수를 찾는 문제였다. 그런데 이 문제는 11724번과 로직이 똑같았다. BFS로 탐색을 진행하면서 탐색이 끝날때마다 카운트를 세면 되는 로직이었다. 가장 기본적인 BFS라고 생각할 수 있다. 그래서 오늘은 BFS에 대해서 간단하게 정리해보려고 한다. BFS란 한국말로 너비우선탐색이다. 너비를 우선..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 오늘 풀은 문제는 간단한 BFS문제였다. 풀었던 문제들과 같은 유형이여서 1트만에 풀어냈다. 단지번호 붙이기 문제와도 비슷하다. BFS로직은 같고 인접리스트를 상하좌우, 대각선으로 해서 탐색을 진행하면 된다. 전체 테이블을 탐색하면서 섬이 있으면 섬의 면적 전체를 방문처리한다. 그리고 다음 섬을 탐색하는 식으로 전체 테이블을 탐색한다. 섬의 수를 세는 로직은 아래와 같다. for(int i=..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 이번에 풀은 문제는 트리구조 관련 문제라고 생각하고 풀었는데, 알고보면 그냥 BFS문제이다. 간단하게 생각하면 된다. 시작 노드를 1로 하고 인접 노드들의 위치에 부모 노드인 1을 집어 넣고, 그 다음 인접 노드에는 1의 자식 노드들을 집어 넣고 하면 된다. 말로하면 이게 무슨 말인가 싶을 수도 있다. 그래서 예제를 따왔다. 예제에서 주어진 입력을 BFS에서 사용하는 간선 추가를 위한 입력으로 생각하고, 시작 노드를 1로 해서 BFS로 탐색을 진행하면, 1과 ..

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개의 줄에 배추가 있는..