늦깎이 IT

[백준 2206번 벽 부수고 이동하기 URL]https://www.acmicpc.net/problem/2206 [비슷한 유형의 문제]2019/02/14 - [알고리즘 문제/백준(BOJ)] - [백준 1194번] 달이 차오른다, 가자. 이 문제를 풀기위해서 고려해야할 사항은 다음과 같습니다. 1. 벽을 한번도 부수지 않고 이동하는 경우와 벽을 한번 부수고 이동하는 경로를 따로 체크해야합니다. 2. 2차원 배열 visited가 아닌 3차원 배열 visited[2][row][col]을 선언하여 벽을 부수지 않고 이동하는 경우는 visited[0][row][col]에 방문체크를 하고 벽 하나를 부수고 이동하는 경우에는 visited[1][row][col]에 방문체크를 해줍니다. 3. Node 클래스의 jump ..

[백준 1194번 달이 차오른다, 가자. URL]https://www.acmicpc.net/problem/1194 이 문제를 풀기위해 생각해야 하는 것은 크게 2가지가 있습니다.1. 획득하는 열쇠 정보를 어떻게 update하고, 문을 만날때마다 어떻게 확인할 것인가??2. 다른 탐색문제들과는 달리 이미 지나온 길을 다시 되돌아가야하는 경우가 발생합니다. [열쇠정보 저장하기]a부터 f까지의 열쇠는 A부터 F까지의 문을 열 수 있습니다.열쇠를 획득할 때마다 획득한 열쇠정보를 저장할 수 있어야합니다. 열쇠정보를 저장하는 방법은 "비트 마스크"로 표현하는 방법이 있습니다. 각각의 열쇠를 비트와 십진수로 표현하면 아래와 같습니다. 열쇠 비트 표현 십진수 a0 0 0 0 0 1 1 b 0 0 0 0 1 0 2 c ..

[백준 11559번 Puyo Puyo URL]https://www.acmicpc.net/problem/11559 문제를 풀기위해 생각해야할 것은 다음과 같습니다. 1. 상하좌우 인접한 뿌요가 4개 이상일 경우 터진다.이 조건으로 인해 BFS탐색을 하면서 각 뿌요의 좌표를 저장해야 합니다. 뿌요의 수가 4개 이상일 경우에는해당 뿌요들의 자리를 '.' 으로 교체하는 것이 뿌요를 터뜨리는 행위입니다.그렇기 때문에 뿌요의 좌표와 갯수를 파악하기 쉬운 자료구조는 List입니다. 2. 한 라운드에 4개 이상인 뿌요가 여러 개 있다하더라도 연쇄반응은 1회로 간주한다.이 조건으로 인해 반복문을 돌릴 때 연쇄반응을 카운트하는 ans 변수의 증가 타이밍을 잘 잡아야 합니다. 3. 한 라운드가 끝난 뒤에 남아있는 모든 뿌요..

[백준 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 메소드..

오늘은 BFS와 DFS의 기초 개념부터 차근차근 설명하려고 합니다.(해당 포스트는 BFS와 DFS의 개념을 모르는 초보분들을 초점으로한 포스팅입니다.) 2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -2 지난 포스팅에서 각 정점들의 연결정보를 1) 인접행렬과 2) 연결 리스트에 저장하는 방법을 살펴보았습니다. 이번 포스팅에서는 이를 토대로 직접 DFS와 BFS를 구현해보겠습니다. 1. 깊이우선탐색 (DFS) 깊이우선탐색은 스택 혹은 재귀호출을 통해 그래프를 순회하는 방법입니다.깊이우선탐색은 우선 나(현재 노드)를 먼저 방문하고 나와 연결된 다른 놈들 중 하나를 방문하는 것입니다.(단, 방문했던 노드는 방문하지 않는다.) 다음과 같은 정점과 간선이 있을 때, DFS 했을 경우의 ..

[백준 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를 대입하고 답을 출력합니다. ..