목록그래프 (168)

1일1알

백준 2583번 영역 구하기 C++

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

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

파이프를 오른쪽으로 옮길 때에는 현재 위치에서 오른쪽 한 칸이 비어있어야 하고 아래로 옮길 때에는 아래에 한 칸이 비어있어야 한다. 대각선으로 옮길 때에 주의해야할 점이 있는데, 대각선으로 간 칸과, 그 위칸과 왼쪽 칸 모두 비어있어야 한다는 것이다. 문제에도 비어있어야 할 칸이 색으로 칠해져있다. 나는 구조체를 만들어서 파이프의 위치와 현재 상태(오른쪽, 대각선, 아래 중 하나) 정보를 저장하고 그 구조체를 큐에 넣어서 bfs방식으로 해결하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; str..
알고리즘 2021. 10. 22. 12:16
백준 12851번 숨바꼭질2 C++

bfs로 풀 수 있는 문제인데 특이한 점은 가장 빠른 시간만 구하는 게 아니라 그 방법이 몇 가지인지까지 구해야 한다. 최초 도달했을 때 시간을 구하고 그 시간과 같은 시간에 도착 할때마다 Count를 증가시켜주면 된다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; vector visited(100001, false)..
알고리즘 2021. 10. 20. 12:46
백준 16953번 A->B (C++)

bfs로 문제를 해결하였다. 초기 cnt=1 처음 큐에 pair로 (A, cnt)을 넣고 (A * 2, cnt + 1) 와 (A * 10 + 1, cnt + 1)을 bfs로 탐색하면서 A의 값이 B의 값과 같아지면 cnt를 출력하는 방식으로 해결하였다. 같은 숫자를 또 방문하는 것을 방지하기 위해 탐색 시간 복잡도가 O(1)인 unordered_set에 방문한 값을 넣어줘서 중복을 방지하고, A * 2나 A * 10 + 1이 B보다 커지면 큐에 넣지 않는 식으로 구현하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef lo..
알고리즘 2021. 10. 19. 10:45
백준 11725번 트리의 부모 찾기 C++

그래프, 트리 관련 문제이다. 우선 (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] 을 탐색하면서 원소가 아직 방문이 되지 않았을 경우에 해당 원소를 큐에 ..
알고리즘 2021. 10. 17. 12:39
이전 Prev 1 ··· 25 26 27 28 Next 다음