1일1알

직사각형의 경로에서 동그라미가 주어지면 그 곳을 거쳐서 오른쪽 밑 끝까지 가고, 주어지지 않으면 그냥 오른쪽 밑 끝까지 가는 경우의 수를 구하는 문제이다. 동그라미의 좌표가 주어지지 않으면 (0, 0)에서 (n-1, m-1) 까지의 경우의 수를 구하고 동그라미의 좌표가 (x, y)라고 주어지면 (0, 0)에서 (x, y) 경우의 수와 (x, y,)에서 (n-1, m-1)까지의 경우의 수를 곱하면 된다. 동그라미는 좌표가 아닌 숫자로 주어지기 때문에 좌표로 변환해야 한다. 숫자가 k로 주어지면 ( (k - 1) / m , (k - 1) % m ) 의 식을 통해 좌표를 구할 수 있다. bfs방식을 통해서 경우의 수를 구하였다. #include #include #include #include #include ..

bfs로 해결할 수 있는 문제이다. 처음에 좌표의 시작점이 왼쪽 아래 (0, 0) 이라 조금 헷갈렸지만 그냥 배열처럼 왼쪽 위 (0, 0)에서 시작해도 결과는 같다. 모양은 위아래로 뒤집어진 모양이 나오지만 영역의 개수와 넓이에는 변화가 없을 것이니 그렇게 해결하기로 했다. 두 번째 줄부터 x1, y1, x2, y2의 좌표가 주어지는데, x는 열, y는 행의 좌표이기 때문에 row1 = y1 col1 = x1 row2 = y2 col2 = x2 라고 저장한 뒤 이 좌표로 둘러싸인 직사각형의 공간을 채워졌다고 표시하고, bfs방식으로 해결하였다. visited 배열을 만들기 귀찮아서 방문한 좌표는 채워졌다고 변경하면서 탐색하였다. 직사각형을 돌면서 채워지지 않은 곳을 발견하면 cnt를 올리고 size를 1..

bfs로 해결할 수 있는 문제이다. 입력을 받은 영역 중에 가장 높은 영역을 max_height 이라고 저장한 뒤, 비가 안오는 경우부터 비가 max_height까지 오는 경우를 모두 검사해서 안전 영역이 제일 많은 경우를 찾았다. 각 지역에 홍수가 났는지를 알려주는 isFlood 2차원 벡터를 만들고 비의 높이에 따라 Init 함수를 통해 isFlood를 초기화 해주었다. 그리고 탐색할 때 visited 배열을 따로 만들기 번거로워서 방문한 안전 영역을 홍수가 난 곳으로 바꿔주면서 탐색을 하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace s..

그래프, 트리 관련 문제이다. 우선 (n+1)*(n+1) 행렬을 만들어서 트리를 인접 행렬을 통해 나타내는 방식을 생각해볼 수 있다. 노드가 양방향으로 연결되어있기 때문에 (1,6)을 받으면 (1,6)과 (6,1) 모두 저장한다. 하지만 이런 방식으로 풀면 비어있는 공간도 모두 탐색하면서 시간이 오래 걸려 시간 초과가 날 것 같아서 다른 방법을 생각해보았다. 2차원 벡터를 사용하여 노드와 연결된 노드만 저장하는 방식이다. vector[1] : 4, 6 vector[2] : 4 .... 이런식으로 만들었다. 우선 루트가 1이라고 했으니 큐에 1을 넣고 시작한 뒤 노드 r을 1로 저장하고 pop을 한번 해준다. 그리고 vector[r] 을 탐색하면서 원소가 아직 방문이 되지 않았을 경우에 해당 원소를 큐에 ..