시간 날 때, 끄적끄적

문제 설명 배추가 심어진 위치는 1, 심어지지 않은 위치는 0으로 표시되어 주어진 map에서 서로 인접한 배추들의 집합이 몇 개 있는지 확인하는 flood fill 문제 고민한 부분 flood fill 문제는 어떤 칸에 연결된 영역을 탐색하는 알고리즘이다. 구현은 BFS나 DFS 등 그래프 탐색 알고리즘을 반복 사용해 풀이하는 것이 많은 것 같다. 이 문제에서는 배열에서 연결된 배추들의 영역의 수를 세야 한다. 이를 위해 배열을 차례로 탐색하며 배추가 심어진 위치에 도달했을 때 BFS 알고리즘으로 인접한 영역을 탐색하고 BFS 실행 횟수를 반환하도록 구현했다. 이미 탐색한 영역을 중복 count하는 것을 방지하기 위해 어떤 표시를 해야했다. 배추 밭과 같은 크기의 배열을 만들어 표시를 할 수도 있지만 배..

문제 링크 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제 설명 일정한 규칙에 따라 이동하는 주사위가 획득하는 점수를 계산하는 문제 주사위 방향을 전환하는 규칙과 주사위의 숫자를 바꾸는 규칙만 이해하면 어렵지 않게 풀 수 있는 문제 고민한 부분 주사위의 상태를 나타내기 위한 방법을 고민했다. 다른 분들의 풀이를 보면 길이 6의 list로 만들어 index별로 의미를 부여해 문제를 해결했는데 나는 헷갈려서 각각의 위치에 해당하는 6개의 변수를..

그래프와 탐색 알고리즘 그래프는 대상들의 관계를 나타낼 때 적합한 자료구조로 대상 나타내는 node 또는 vertex들과 그들의 연결 관계를 나타내는 Edge로 표현할 수 있다. 그래프는 edge가 탐색할 수 있는 방향의 존재 여부와 가중치의 여부에 따라 크게 네 가지 종류로 구분할 수 있다. 무향 그래프 : edge의 방향이 없는 그래프 유향 그래프 : edge에 방향이 있는 그래프 가중치 무향 그래프 : edge에 방향은 없으나 가중치가 있는 그래프 가중치 유향 그래프 : edge에 방향과 가중치가 있는 그래프 행렬의 행은 출발하는 node의 숫자, 열을 도착하는 node의 숫자로 그래프를 표현할 수 있다. 아래의 예는 유향 그래프를 행렬로 표현한 것을 나타낸 예시이다. 1번 node는 2와 3으로 ..

문제 링크 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 문제 설명 일정한 규칙에 따라 이동하는 주사위가 획득하는 점수를 계산하는 문제 주사위 방향을 전환하는 규칙, 점수를 계산하는 규칙을 꼼꼼하게 읽고 풀이하면 어렵지 않게 풀 수 있는 문제 고민한 부분 주사위의 상태를 나타내기 위한 방법을 고민했다. 다른 분들의 풀이를 보면 길이 6의 list로 만들어 index별로 의미를 부여해 문제를 해결했는데 나는 헷갈려서 각각의 위치에 해당하는 6개의 변수를 만들어 주사위를 modeling하는 것이..

문제 링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 설명 빈 공간, 벽, 바이러스로 구성된 2차원 array를 입력받아 빈 공간 세 곳에 벽을 세운 후 바이러스가 퍼질 수 없는 영역의 수를 세는 문제 구현해야 하는 내용은 빈 공간에 $^{1)}$세 개의 벽을 세우는 것, $^{2)}$바이러스가 퍼질 수 있는 영역을 BFS로 탐색하는 것, $^{3)}$감염되지 않은 영역을 세는 것 고민한 부분 아직 순열이나 조합을 응용하는 문제에 익숙하지 않아 긴 시간동안 고민을 했음 재귀 방식으로 3개의 블럭을 쌓은 후 BFS..