목록백준/bfs, dfs (47)
Study hard
www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net [풀이] 문제에 있는 규칙대로 구현하면 되는 문제였다. 구현 순서 1. 국경선 열기 2. 인구 이동 3. 연합 해체, 국경선 닫기 1. 국경선 열기 - vectorUnion[1250]을 선언하여 사용하였다. (County 구조체는 나라의 위치와 인구수 포함, 1250은 50*50배열에서 나올 수 있는 최대 연합의 수) - dfs를 이용해서 서로 인접한 나라의 인구 수 차이가 L이상 R이하인 경..
www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net [풀이] 문제에 주어진 규칙대로 구현하면 되는 문제였다. 1. 감시카메라들 방향 결정 2. 감시구역 표시 3. 사각지대 크기 구해서 최솟값 갱신 1. 감시카메라들 방향 결정 - dfs로 모든 감시카메라들의 방향 경우의 수를 탐색 - 처음에 사무실 상태를 입력 받으면서 감시카메라 위치와 종류를 벡터에 동시에 저장하였다. - 벡터에 저장한 순서대로 감시카메라 방향을 결정하였다. - 방향은 cctvDi..
www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net [풀이] 2020상반기 인턴 sw역량테스트에 나왔던 문제다. 1번 문제 푸느라 제대로 풀지 못했다.. 다음과 같은 순서로 구현하였다. 1. 가까운 승객 찾기 2. 승객에게 이동: oil-출발지까지 이동거리, 택시 위치 승객 출발지로 3. 목적지로 이동: oil-목적지까지 이동거리 4. 남은 오일이 0보다 작으면 -1출력 후 끝, 0 이상이면 oil+목적지까지 이동거리*2 ..
www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net [풀이] dfs 순열 구하는 방법을 이용하여 회전 연산 순서를 정했다. ※r, c가 1부터 시작한다는 것 유의 회전 연산은 값 하나를 tmp에 저장해놓고 for문을 돌리는 방식으로 구현했다. #include #include //min #include using namespace std; struct Roll { int r, c, s; }; int N, M, K; int A[51][..
www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종� www.acmicpc.net [풀이] dfs 순열 구하는 방법을 이용하여 타순을 구하고 게임 룰대로 시뮬레이션 하면 되는 문제였다. 1. 타순 구하기: 순열 2. 각 타순에 대하여 나올 점수 구하기 3. 최댓값 갱신 ※다음 이닝으로 넘어갈 조건, 타순 만드는 조건 등 주위깊게 보기! #include #include using namespace std; int N; int Results[50][10]; int Order[10]; bool che..
www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크�� www.acmicpc.net [풀이] dfs를 이용하여 백트래킹을 하였다. 1. 종이에서 1 찾기: 1 없으면 지금까지 붙여왔던 종이 개수와 최솟값 비교하여 갱신 2. 1이 있는 칸에 1*1, 2*2, 3*3, 4*4, 5*5 종이를 붙일 수 있는지 확인(종이 붙이는 범위 안에 0이 있으면 안 됨) 3. 종이를 붙이고 붙인 종이 개수에 +1하여 재귀 4. 붙인 종이 떼기 #include #include using namespa..