늦깎이 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 메소드..

[백준 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번 노드..