본문 바로가기

전체 글

 (371)
[BOJ] 16932. 모양 만들기 * dfs를 이용하여 1로 이루어진 그룹을 라벨링한다. (그룹에 몇 개의 1이 있는지 labelCnt[]에 저장한다) * 현재 좌표의 값이 1이고, 상 하 좌 우 인접한 값이 0인 좌표를 중심으로 탐색을 한다. 인접한 좌표에 0이 있다면 이 값을 1로 바꾸고 다른 그룹들과 합쳐질 수 있다. -> 이를 가능하게 하려면, 0인 좌표의 인접한 칸에 다른 그룹이 있어야 한다. * 만약, 0인 좌표가 다른 그룹과 인접해 있다면 (연합 그룹을 형성하는 1의 개수와 현재 그룹의 개수 +1 )의 최대값이 정답이 된다. * 주의해야 할 점은, 0이 같은 그룹으로 이루어진 1들로 둘러싸여져있을 수 있기 때문에 중복으로 더해주는 것을 방지해야 한다. (set에 그룹의 라벨을 넣어주어서 중복으로 세지 않도록 하였다. ) 1 ..
[BOJ] 17822. 원판 돌리기 * rotate에서는 x의 배수인 원판들을 시계/반시계 방향으로 k번 회전한다. * deque를 사용해서 시계방향은 한 원판에서 가장 뒤에 있는 요소를 가장 앞에 삽입한다. (pop_back -> push_front) 반시계방향은 가장 앞에 있는 요소를 가장 뒤에 삽입한다. (pop_front->push_back) * deque에 저장된 값들을 다시 map에 넣는다. * removeNums()에서는 인접한 숫자들을 지운다. 만약, 전체 원판을 통틀어 지울 수가 없다면 평균값에 따라 원판의 값을 조절한다. * 각 좌표에서 상 하 좌 우를 살펴봤을 때 같은 수가 있으면 큐에 넣어준다. 만약, 전체 원판을 봤을 때 큐에 아무런 값도 없다면 지울 값이 없다는 것이다. * *평균값을 double로 구해줘야 한다...
[BOJ] 16918. 봄버맨 * bombTime[] 폭탄이 설치되는 시간을 저장한다. * 처음 1초 동안 봄버맨은 아무것도 하지 않는다. -> n == 1일 때 입력받은 폭탄을 그대로 출력해야 한다. * 1초 동안 폭탄이 없는 곳에 폭탄을 설치한다. (이때 설치하는 폭탄은 first (처음 폭탄이 터지는 시간) + 2 시간에 터진다. ) * 1초 프로세스 도중에 sec == n이 되면 실행을 멈춘다. * 폭탄을 터트린다. (bomb(터질 폭탄 -> 이 시간에 터질 폭탄만 터트린다)) -> 1초 소요 * 폭탄은 터질 때 주변의 폭탄들을 같이 터트리기 때문에 자신과 같은 숫자를 가진 폭탄은 터트리지 않는다. * 주변의 폭탄을 터트린 후에 현재 터져야 할 폭탄들을 터트려준다. (62 ~ 72 line) #include #include u..
[BOJ] 9328. 열쇠 * BFS로 완전 탐색을 한다. * 열쇠 상태를 계속 저장한다. (keystate) * 상근이는 빌딩 밖을 자유럽게 돌아다닐 수 있기 때문에 맵의 바깥쪽은 전부 '.'으로 만들어준다. *(0,0)부터 탐색을 시작한다. - 문을 만나면 지금 가지고 있는 키로 열 수 있는지 확인한다. 열 수 있다면 빈공간('.')으로 만들어준다. - 문서를 만나면 훔칠 수 있는 문서의 개수인 (res)를 1만큼 증가시키고 빈공간('.')으로 만들어준다. - 열쇠를 만나면 keystate를 비트마스킹을 이용하여 값을 변경해주고 빈 공간으로 만들어준다. - 여기서 중요한 것은 열쇠를 만났을 때 지금 까지 방문했던 좌표 중에 이제는 열 수 있는 문이 있을 수도 있기 때문에 visited 배열을 초기화한다. (초기화하는 방법 말고..
[BOJ] 14391. 종이조각 * (0,0) ~ (n-1, m-1) 까지 완전 탐색하면서 백트래킹으로 전수조사를 한다. * 방문 표시 된 좌표는 가로로 숫자를 만드는 부분이고, 방문 표시가 안 된 부분은 세로로 숫자를 만드는 부분이다. T T T T 이렇게 방문표시가 되어있다면 이렇게 방문 표시가 된 부분은 가로로 직사각형을 만들고. 아닌 부분들은 세로로 직사각형을 만든다. * 이어지는 숫자를 string으로 만들어서 sum에 누적합을 해 준다. #include #include #include using namespace std; int n, m; char map[5][5]; int dx[2] = {1, 0}, dy[2] = {0, 1}; bool visited[5][5]; int ans = 0; bool chk[5][5]; int ..
[SW Test 샘플문제] 프로세서 연결하기 * dfs 조합을 이용해서 최대한 많은 core들을 연결했을 때 최소 전선의 길이를 구한다. * 맵의 사이드에 있는 코어들은 이미 연결되어있기 때문에 cores에는 그 외의 코어들을 넣는다. * dfs(idx, cnt)에서는 코어들을 조합을 확인하면서 백트래킹한다. * check(x, y, d) : x, y 좌표에 있는 코어가 d방향으로 연결될 수 있으면 T, 아니면 F doConnect(x, y, d) : check() 가 T라면 연결한다. (chk 배열에 방문표시) doDisConnect(x, y, d) : 원상 복귀 (백트래킹) #include #include #include #define INF 987654321 using namespace std; int n; int map[13][13]; bo..
[SWEA] 보물상자 비밀번호 [문제] https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com [풀이] 1.convertToDe() => (문자열 사이즈 /4)를 한 길이의 문자열 4개를 10진수로 바꾸어서 int 배열에 저장한다. (16진수임을 명시 해야 함.) 백터에 정수들을 저장 2. rotate() => 입력받은 문자열의 가장 마지막 문자열을 맨 앞으로 가져온다. (한 문자씩 시계방향으로 움직이기 때문에 각 회전마다 변경되는 건 맨 뒤의 문자열 뿐이다.) 3. 백터를 ..
[BOJ] 1600. 말이 되고픈 원숭이 * 최단 거리가 정답이 아닐 수도 있다. * 1 3 5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 처럼 도착 지점이 장애물로 막혀져있는 경우 0 0 0 x 0 0 0 x 0 1 0 0 0 1 0 x로 표시되어있는 지점까지 원숭이로 이동한 후 말의 이동을 하는 방법이 도착할 수 있는 최선의 방법이다. * 큐에는 4가지 값이 들어간다. {움직인 횟수, 말로 움직인 횟수, 좌표} 말로 움직인 횟수가 k보다 작을때까지만 말로 움직인 좌표를 큐에 넣을 수 있다. 원숭이로 움직인 횟수는 항상 넣는다. (최단 경로 != 정답) *코드가 깔끔하지 않다. *dx / dy => 상하좌우 cdx / cdy => 대각선 #include #include #include #define INF 987654321 usin..

티스토리툴바