https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 난이도 : 골드 2 태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 삼성 기출문제로도 유명한 상어 시리즈 중 상어 중학교 입니다. 다른 상어 시리즈와 마찬가지로 시뮬레이션 + 그래프(탐색 및 백트래킹) + 배열 뒤집기가 인상적이였던 문제였습니다. 계속 테스트케이스가 다르게 나왔는데, 시뮬레이션 문제 특성 상 한 회차당 맵이 어떻게 바뀌는지 확인해야 하기 때문에 엑..

https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 각 플레이어 i는 한 턴에 S(i) 거리 만큼 확장을 할 수 있습니다. 각 플레이어 별로, 그리고 한 싸이클씩 그래프 탐색을 진행하는게 포인트라 할 수 있습니다. 예제중 하나를 가져와봤습니다. 초기 상태가 아래와 같고, 플레이어 1이 2칸, 플레이어 2가 1칸씩 움직일 수 있는 경우입니다. 1..1 .... .... ..

https://level.goorm.io/l/challenge/goormthon-challenge?utm_source=notion&utm_medium=cta&utm_content=open&_gl=1*1lv0w8b*_gcl_au*MTA2NTY4MTU0My4xNjkyMDE0OTc4 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 구름톤 알고리즘 챌린지? 이번엔 조금 재밌는 챌린지를 하게 되었습니다. 구름(구름 LEVEL) 에서 진행하는 구름톤 알고리즘 챌린지인데요. 조금 늦게 알게 되었지만 챌린지가 종료되기 전에라도 알게되어 다행입니다. 😀 이번 포스팅에서 다룰 문제는 챌린지 17일차 '통신망 분석' 입니다. 일반적인 DFS/BFS를 활용한 그..

https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 난이도 : 골드 2 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 3차원 큐브를 탈출하는 문제입니다. 한 층씩 좌우로 층을 회전할 수 있고, 한 층씩 마음대로 쌓을 수 있기 때문에, 각 층을 회전하여 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS) 1번, 각 층을 쌓아 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS..

그래프 탐색 정점(Node, Vertex)과 간선(Edge)로 이루어진 그래프. 이 그래프를 탐색하는 방법에는 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search) 입니다. 물론 다른 그래프 탐색 알고리즘도 존재하나, 이 둘이 가장 유명한 방법이지 않을까 싶네요. 깊이 우선 탐색 (DFS, Depth - First Search) DFS는 깊이 우선이라는 이름처럼 깊이를 우선적으로 탐색합니다. 한 노드의 연결된 노드를 먼저 탐색한다는 의미죠. 해당 그래프를 DFS로 탐색한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서로 탐색합니다. 한 노드를 탐색할 때, 해당 노드와 연결된 ..

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프탐색, 그래프이론, 너비우선탐색 설명 한 좌표에 다른 좌표의 불을 켤 수 있는 스위치가 있습니다. 복수개일 수 있으며, 스위치를 총 몇 개나 작동시킬 수 있는지(불을 킬 수 있는지)를 구하는 문제입니다. BFS를 사용하면 될 것 같지만, 스위치를 켜서 갈 수 있는 좌표가 늘어남에 따라, 해당 좌표와 인접한 좌표..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 특정 위치로 이동할 수 있는 가장 적은 횟수를 찾는 문제입니다. bfs를 활용할 수 있겠는데요. 단순히 4방향 bfs가 아닌 나이트의 이동에 맞춘 8방향 bfs를 사용하면 될 것 같습니다. 나이트의 이동은 상,하,좌,우 중 2칸 이동하고, 수직방향으로 1칸 혹은 상하좌우 1칸 이동 후 이동방향의 대각선 방향 1칸 이동으로..

https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 몇 개의 역이 튜브로 연결되어 있고, 1번에서 N번까지 가는데 거쳐야 하는 최소 역 개수를 찾는 문제입니다. 시도 1 음... 각 튜브들끼리 연결되있다고 하니까, 단순히 각 튜브들끼리 모든 순서쌍을 그래프를 만들면 풀리지 않을까요? (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색 설명 가중치가 있는 그래프(트리)에서, 두 노드간 거리를 구하는 문제입니다. DFS/BFS를 사용해 그래프(트리)를 탐색하여 풀 수 있을 것 같은데요. 저는 BFS를 사용해 풀이하였습니다. 소스코드 데이터용 클래스 Node Node는 to (목표 노드), cost(목표 노드로 가는..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 얼음을 녹이면서 덩어리가 두개가 되는 시점을 찾는 문제입니다. 얼음을 녹이는 구현 부분에 약간의 시뮬레이션 요소가 들어갔다고 볼 수 있을 것 같네요. 얼음이 몇 덩어리인지 확인하는 부분은 DFS / BFS 를 사용할 수 있을 것 같은데, 저는 DFS를 사용해 풀이하였습니다. 접근 방법 1...