코딩 공부하는 코딩류

비가 내렸을 때 물에 잠기지 않을 지역의 최대 갯수를 구하는 문제 문제의 조건 1. 어떤 지역의 높이 정보가 위와 같이 주어진다. 2. 비가 4만큼 오면 위와 같이 높이가 4 이하인 지역은 모두 물에 잠긴다. 3. 이 때 하얀 부분을 물에 잠기지 않는 안전 영역이라 할 수 있는데 같은 안전 영역의 범위는 상하좌우로 맞닿은 영역들만 포함한다. 즉 이런 경우처럼 대각선 방향으로 맞닿아 있는 영역은 같은 안전 영역이라 할 수 없다. 2번의 경우에서 안전 영역의 갯수는 5개이다. 4. 6만큼 비가 와서 높이가 6 이하인 지역이 모두 물에 잠긴다면 위와 같이 나타낼 수 있다. 이 때 안전 영역의 갯수는 4개이다. 이 지역에서 비가 오는 양 별로 안전 영역의 갯수를 모두 확인해 봤을 때 최대 갯수는 5개이다. 5...

지도에 표시되어 있는 섬의 개수를 세는 문제 문제의 조건 1. h의 높이 x w의 너비 크기를 가진 지도가 주어진다. 2. 2차원 지도 배열에는 0과 1로 표시가 되어 있다. 0은 바다, 1은 땅이라는 뜻 3. 2차원 배열의 각 땅들은 상하좌우 대각선으로 연결되면 하나의 섬이라고 할 수 있다. 4. 여러 테스트 케이스가 주어질 때 각 테스트 케이스의 섬의 갯수를 구해서 출력하기 5. 입력의 마지막 줄에는 0 0 이 주어진다. 입력받은 w와 h가 둘 다 0이라면 테스트 케이스 입력받기 종료하고 프로그램도 종료 풀이 과정 BFS로 상하좌우에 연속되어 있는 같은 숫자 갯수 세던 문제에서 대각선 방향만 추가해서 풀면 될 거 같아서 기존 BFS 코드에 대각선 방향만 추가해서 풀었습니다. 1. 방향 확인용 배열에 ..

방향이 없는 연결 그래프에서 서로서로 연결된 덩어리가 몇 개인지 구하는 문제 문제의 조건 1. 첫째 줄에 N개의 정점을 가진 양방향 연결 그래프와 M개의 간선이 주어진다. 2. 둘째 줄부터 간선의 양 끝점이 주어진다. 3. 서로 연결된 요소가 몇 개인지 출력 풀이 과정 앞전에 풀었던 컴퓨터 바이러스 문제처럼 몇 개의 정점이 간선을 통해 서로 연결되어 있는지 확인하면 될 거라고 생각했습니다. 연결 요소라는 말이 헷갈렸는데 질문 게시판 보니까 컴퓨터 바이러스 문제처럼 간선으로 서로서로 연결된 것들을 한 덩어리로 치는 것이 맞더라고요. 풀이 1. 양방향 그래프를 만든 뒤 BFS로 현재 정점에서 방문할 수 있는 곳들을 모두 방문한다. 2. 1번 과정이 끝나고 나면 한 연결 요소(덩어리) 탐색이 끝난 것이기 때문..

배추밭에 필요한 배추흰지렁이의 최소 갯수를 구하는 문제 문제의 조건 1. 배추를 해충으로부터 보호하기 위해 배추밭에 배추흰지렁이를 놓을 것이다. 2. 지렁이는 상하좌우에 인접한 배추에게 이동할 수 있다. 3. 배추는 한 번에 많이 몰려있지 않고 밭 전체에 퍼져서 심어져 있다. 아파트 단지처럼 배추도 단지별로 심어져 있음 4. 필요한 지렁이의 최소 갯수 구해서 출력하기 5. 테스트 케이스가 여러 개 주어질 수 있다. 풀이 과정 1. BFS로 배추밭을 탐색하는데 전체 밭을 탐색해야 하기 때문에 2중 for문으로 [0, 0]번째부터 탐색한다. 2. 배추 한 칸을 대상으로 상하좌우에 또 배추가 있는지 검사해서 연결된 배추가 있으면 다음에 방문할 큐에 추가 3. 하나의 배추 단지 검사가 끝나고 나면 정답 카운트를..

서로 연결되어 있는 컴퓨터 중에서 바이러스에 감염된 컴퓨터가 몇 개인지 구하는 문제 문제의 조건 1. 컴퓨터의 갯수 N, 서로 연결된 쌍 M개가 주어진다. 2. 1번 컴퓨터는 바이러스에 걸렸는데 이 바이러스는 네트워크를 통해서 전파된다. 3. 1번 컴퓨터부터 시작해서 서로서로 연결되어 있는 컴퓨터들은 연결된 컴퓨터에게서 바이러스가 옮았다. 4. N개의 컴퓨터 중에서 1번 컴퓨터를 빼고 몇 개의 컴퓨터가 바이러스에 걸렸는지 출력 풀이 과정 쉽게 생각하고 시작했는데 생각보다 오래 걸린 문제 ㅠ.ㅠ 아직 dfs/bfs가 완벽하지 않아서 그런가 봅니다. 단순하게 모든 정점을 탐색하는 코드는 쉽게 짤 수 있지만 조금만 응용되어 나오면 방문할 필요가 없는 정점을 어떻게 거르나 고민하면서 시간을 많이 썼습니다. 풀이..

전형적인 BFS 문제로 정사각형 맵에서 연속되어 붙어 있는 집(1)들의 덩어리 갯수와 덩어리 안에 집이 몇개나 들어있는지 구하는 문제 문제의 조건 1. NxN 크기를 가진 정사각형 2차원 배열이 주어진다. 2. 2차원 배열에는 0과 1이 들어있다. 0은 아무것도 없는 곳을 뜻하고 1은 집이 있다는 것을 나타낸다. 3. 1들이 상하좌우로 연속해서 붙어 있으면 같은 단지로 친다. 주어지는 2차원 배열에는 단지가 여러개 있다. 4. 첫 번째 줄에 주어진 2차원 배열에 들어 있는 단지의 갯수를 출력하고 두 번째 줄부터 각 단지 안에 있는 집의 갯수를 오름차순으로 정렬해서 출력하기 풀이 과정 DFS 카테고리에 있긴 했지만 BFS로 풀어도 될 거 같아서 큐를 이용해 BFS로 풀었습니다. 한 타일을 기준으로 상하좌우..

아주 전형적인... BFS로 최단 거리를 찾는 문제 문제의 조건 1. N x M 크기의 미로가 주어진다. 2. 미로의 [1, 1]에서부터 [N, M]까지 가는 최단 거리를 구해서 출력하기 => 미로 배열의 [0, 0]에서부터 [N-1, M-1]까지의 최단 거리를 구하면 된다. 풀이 과정 많이 보던 스타일이라 낯설진 않았고 BFS 알고리즘도 어느정도 익숙해서 금방 풀 수 있을 것이라 생각했지만... 여전히 백준 문제의 입력을 받는 것에 익숙하지 않았기 때문에 입력을 받는 과정에서도 착오가 있었고... 최단 거리를 구하는 식을 잘못 썼고... 등등의 이유로 오래 걸린 문제입니다. ㅠ.ㅠ 그래도 덕분에 이젠 확실하게 알겠습니다... 근데 문제에 입력되는 숫자가 붙어서 주어진다 이런 말 말고 string형 배열..

제목 그대로 DFS와 BFS로 그래프를 탐색한 결과를 출력하는 문제 문제의 조건 1. 주어진 그래프를 DFS와 BFS로 각각 탐색한 결과를 순서대로 출력하면 된다. 2. 단, 방문할 수 있는 정점의 개수가 여러 개면 정점의 수가 작은 것 부터 방문한다. 풀이 과정 처음에는 요즘 알고리즘을 공부하고 있는 책에 나와 있는 알고리즘을 썼는데... (대충 엣지 좌우 저장하는 구조체 만들고 전체 그래프를 구성하는 클래스를 만든 뒤 그렇게 만들어진 그래프 클래스를 이용해서 bfs와 dfs를 수행하는 내용 코드 길이가 A4 한 장 정도 됨) 알고 보니 모든 정점이 서로서로 연결되어 있다는 것을 전제로 한 알고리즘이라 이번 문제에는 맞지 않았습니다. 주륵 ㅠ.ㅠ 그리고 제게는 그것을 수정할 능력이 없었습니다...ㅋㅋㅋ..