potato's devlog

✅ 문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ✅ 문제 풀이 아이디어 기본적으로 연합국가인지 아닌지를 판단해야하기 때문에 BFS로 풀어야한다고 생각했다. 위의 출력예제를 보면, 점선이 생기는 위치가 다르다. 30과 40은 직접적인 연결은 아니지만, 어쨋든 연합국가이긴하다. 그렇기 때문에 초반에 어렵게만 생각되었던 "어디에 점선이생기는지 고려해야하는가"를 전혀 생각하지 않고 그냥 탐색하면서 연합국가에 같이 담아주면된..

🟣 문제 링크 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 🟣 문제 풀이 우선 문제를 이해하는데 어려웠다. 그림을 그리면서 + 그리고 인터넷을 찾아보면서 문제를 이해했다. 우선, '순환선 = 사이클'을 찾아야한다. 이 지하철 노선도로 보면, '신도림'역은 이미 순환선 (사이클) 내부에 있기 때문에 순환선까지의 거리가 0이다. 하지만 '까치산'역인 경우, 순환선이 아니라 지선에 속한다. 이 까치산역은 '순환선'까지 ..

💻 문제 링크 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 💻 풀이 BFS로 풀었다. 사실 시작점이 여러개인 BFS는 어떻게 풀어야할지 모르겠어서, 인터넷을 참고해서 풀었다ㅠㅠ m과 n을 입력받는다. 0, -1, 1이 들어있는 배열을 box로 입력받았다. day는 며칠이 지났는지 판단하기 위해서 만든배열이다. 뒤에서 보면 한칸한칸 익어나갈때마다 +1 을 해준다. let mn = readLine()!.split(separato..

💻 문제 링크 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 💻 문제 풀이 기본적이 BFS 문제이다. 미로를 가중치 없는 무방향 그래프로 본다면, 가중치없는 무방향 그래프에서 최단거리를 구하는 BFS 탐색 방법을 이용하면된다! 처음 입력받는 n과 m을 nm 배열로 입력받아서 nm[0], nm[1] 로 사용하였다. dx, dy 는 상하좌우 방향을 나타내는 방향키! 이다. arr는 입력받는 미로 visited는 미로에서 방문했는지 안했는지 T/F 로 나타내는 배열 distanc..

👉 문제링크 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 💻 문제풀이 가장 기본적인 DFS문제 (BFS도 가능) 그래프로 입력 받은 후, 1인 곳을 전부 탐색 → 탐색하면서 해당 위치 방문처리 방문처리 된 곳들을 돌아다니다가 방문처리할 곳이 없으면 count += 1 최종적으로 count 출력 💻 소스코드 https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/4963_%EC%84%A..

💁🏻 문제링크 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 💻 문제 풀이 이런 문제를 만나면, 현재위치에서 위, 아래, 오른쪽, 왼쪽을 살펴보면서 연결이 되어있나? 를 판단해야한다. 위 그림을 보면, 현재 위치는 (0,0)일때 방향키로 움직일 수 있다. x좌표인 0에다가 dx[2]을 더하고, y에다가 dy[2]을 더해주면, (1,0)으로 한칸 아래로 이동할 것이다. 이처럼 이렇게 "연결된 1을 찾아 무언가를 찾는문제"라면, 이렇게 방향키를 생..

👉 문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 🧑🏻‍💻 문제 풀이 이분그래프 이면 1, 이분그래프가 아니면 -1를 flag에 저장해주었다. 정점은 각각 1과 -1로 구별해주었다. 만약 인접한 정점이 둘다 1이거나, 둘다 -1이라면 이건 이분그래프가 아닌거다! 이 값들은 visited 에 넣어주었다. 아래 코드는 main으로 돌아가는 부분이다. 차례대로 설명을 작성해보자면 처음 입력받는 K 만큼 result가 출력되어야 하므로 모..

🙋🏻‍♀️ 이분그래프 위 사진처럼 그래프가 '두개의 색'으로 표현되는 것을 이분그래프라고 한다. 빨간정점과 검은정점 두 그룹으로 나뉘었는데, 같은 그룹끼리는 인접하지 않아야한다. 즉, 그래프의 모든 정점이 두 그룹으로 나뉘어지고 서로 다른 그룹의 정점만이 간선으로 연결된 그래프를 말한다. 👻 이분그래프의 특징 이분 그래프인지 확인하기 위해서는 BFS와 DFS 탐색 방법을 이용할 수 있다. DFS와 BFS를 통해서 그래프를 탐색하게 되면, 같은 depth에 있는 정점은 같은 색을 갖게 되는 것이다. 연결 요소의 개수를 구하는 방법과 유사하다. 모든 정점을 방문해서 검사하기 때문에 시간복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다. 🧑🏻‍💻 이분그래프인지 확인해보는 방법 ⚠️ 주의사항: 서로 인접한 정..

🙋🏻‍♀️ 백트래킹이란? 백트래킹은 모든 경우의 수를 전부 고려하는 알고리즘이다. 일종의 탐색 알고리즘으로, DFS, BFS 로 모두 구현 가능하다. 백트래킹은, 답이 될 수 없는 후보는 더이상 탐색하지 않고 다시 돌아가는 알고리즘이다. 모든 경우의 수를 고려하는 브루트포스보다 더 시간을 절약할 수 있다. 완전탐색의 대표적인 방법에는 DFS가 있다. 재귀를 이용해서 현재시점에서 계속해서 방문할곳을 탐색하고, 방문한다. 반면, 백트래킹은 비효율적인 경로를 차단하고 목표지점에 도달할 수 있는 가능성이 존재하는 곳만 탐색하기 때문에 일종의 가지치기라고도 부른다. 🙋🏻‍♀️ 백트래킹 절차 DFS 수행 - 유망한 노드 검토 - 서브트리 이동 - 백트래킹 수행 1. DFS 수행 : 재귀를 호출하면서 DFS를 그대로..

문제링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제풀이 해당 문제를 풀기 위해서는 완전탐색으로 풀거나, 백트래킹이라는 개념을 이용하는 방법이 있다고 한다. 완전탐색은 말그대로 그래프 전체를 탐색해서 팀원이 됐는지, 안됐는지 판단하는 방법이고, 백트래킹은 "DFS 방법이지만, 어느정도의 depth에 도달하게 되면 탐색중지"하는 알고리즘이다. 백트래킹에 대한 개념을 잘 모르니, 이 문제를 포스팅한 후 백트래킹과 관련한 알고리즘 포스팅을 할 예정이다. 우선 나..