늦깎이 IT

[백준 2234번 성곽 URL]https://www.acmicpc.net/problem/2234 [유사문제]2019/02/11 - [알고리즘 문제/백준(BOJ)] - [백준 2667번] 단지번호붙이기 문제에서 요구한 정답은 총 3가지 입니다.이 성에 있는 방의 개수가장 넓은 방의 넓이하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 여기서 1번, 2번 답은 bfs 메소드를 통해 구할 수 있습니다. 1) 2차원 배열 map을 순차탐색하면서 visited[row][col] == false 일 경우, 아직 방문하지 않았다는 뜻이므로 bfs(row, col) 메소드를 호출합니다. bfs를 호출할 때 마다 roomCnt 변수를 1씩 증가시켜줍니다. roomCnt는 방의 갯수를 뜻합니다. 2) bfs 메소드..

[백준 2667번 단지번호붙이기 URL]https://www.acmicpc.net/problem/2667 1. 이중 for문으로 map 전체를 확인하면서 방문하지 않았고 동시에 1인 곳부터 BFS 탐색을 시작합니다. 2. 한번의 BFS 탐색이 끝나면 하나의 단지가 모두 check됩니다. 총 단지의 수를 의미하는 apart라는 변수를 사용해서 map[row][col] = apart 대입하고 apart를 증가시킵니다. 3. 즉, 한번의 BFS를 통해 인접한 집들을 하나의 단지로 모두 check하고 단지를 의미하는 apart 변수를 통해 총 몇개의 단지가 있는지 확인할 수 있습니다. 4. 1번이 모두 끝났으면 다시 이중 for문을 통해 map[row][col] 값을 체크해서 값이 1이면 1단지, 2이면 2단지..

[백준 7576 URL]https://www.acmicpc.net/problem/7576이번 문제는 전형적이고 아주 쉬운 탐색문제입니다.하지만, [백준 2178번 미로탐색]과는 다르게 함정(?)이 숨어있습니다.2019/02/11 - [알고리즘 문제/백준(BOJ)] - [백준 2178번] 미로탐색 1. 데이터를 입력받는 map, 방문처리를 위한 visited 배열을 선언합니다. 2. 행과 열, 그리고 몇번을 움직였는지 count하기 위해 Node 클래스를 선언합니다. 3. 입력을 받을 때 map[row][col] == 1 인 경우는 익은 토마토이므로 tomato라는 List에 추가시켜줍니다.그 이유는 익은 토마토들과 인접해있는 익지 않은 토마토들부터 익기시작하기 때문에 Queue에 초기에 입력받은 토마토들..

[백준 2178 URL]https://www.acmicpc.net/problem/2178 이번 문제는 전형적이고 아주 쉬운 탐색문제입니다.2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1 단순히 방문 체크를 해주는 조건에 map[row][col] == 1 인 경우에만 탐색할 수 있는 조건을 넣어줍니다. 1. 데이터를 입력받는 map, 방문처리를 위한 visited 배열을 선언합니다.2. 행과 열, 그리고 몇번을 움직였는지 count하기 위해 Node 클래스를 선언합니다.3. [0][0]의 위치에서 Queue를 이용하여 BFS를 수행합니다.4. Queue에서 하나씩 꺼내면서 해당 Node의 행과 열 값이 각각 N-1과 M-1일 경우 ans에 cnt를 대입하고 답을 출력합니다. ..

[백준 1260번] DFS와 BFS 소스 코드입니다. [백준 1260번 URL]https://www.acmicpc.net/problem/1260 DFS와 BFS의 기본 개념을 알고 싶으신 분은 클릭해주세요.2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1 1. 각 노드간의 연결 상태는 vector에 저장한다.예를 들어, 0번 노드와 연결된 경우 graph[0]에 차곡차곡 저장한다.즉, 0번 노드와 연결된 노드의 갯수는 graph[0].size()이다. 2. 각 노드간의 연결상태를 저장했다면 visited 배열을 통해 차근차근 방문한다.반복문을 통해 graph[0]부터 차근차근 접근한다. 예시)graph[0] 에 저장된 값이 1, 2, 3이라면 0번 노드와 1, 2, 3번 노드..