본문 바로가기
반응형

[백준]214

[BaekJoon/백준] 2146번 다리 만들기 SCC 관련 문제가 많이 나오는 것 같다. 16234번 인구이동, 2234번 성곽 문제처럼 SCC 그룹을 정의하여 푸는 문제였습니다. DFS로 SCC를 정의하고 BFS로 다리 최단길이를 정해주었습니다. 즉, 처음 DFS를 통해 각 섬의 종류를 분류하여 SCC 배열에 저장해주고 BFS를 통해, 다른 섬에 닿을때의 최솟값을 계산해줍니다. 주석을 풀어서 실행해보시면 이해에 도움이 되실 수 있을 것 같습니다. #include #include #include using namespace std; int N; int MAP[100][100]; int SCC[100][100]; int DEPTH[100][100]; bool VISIT[100][100]; int mx[4] = {0, 0, -1, 1}; int my[4.. 2022. 7. 23.
[BaekJoon/백준] 3190번 뱀 문제에서 하라는 대로 해주면 되는 시뮬레이션 문제였다. 구현하기에 수월하다고 생각되는 방식은, deque를 이용하는 것이었다. 앞/뒤로 push,pop이 가능한 deque를 이용해서, 뱀의 좌표를 저장하며 구현했다. 반복문 종료 조건에는 두 가지가 있다 맵을 벗어난 경우 뱀의 몸통에 부딪힌 경우 bool VISIT을 이용해서, 현재 방문처리를 진행했고 deque를 이용해서, 뱀이 차지하고 있는 좌표들을 저장했다. #include #include #include // 직접 배열을 구현해서 시뮬레이션 하는 방법과, 숫자로만 계산하는 방법이 있겠다. // => 맵을 벗어나는 처리를 해주기 위해선,, 숫자로만 계산하는 방법으론 안되겠구나..! using namespace std; int N, K, L, CONT.. 2022. 7. 22.
[BaekJoon/백준] 14499번 주사위 굴리기 이 문제의 가장 큰 관건은, 주사위 시뮬레이션이다. 그리고 어떻게 주사위를 표현할까? 라는 고민을 해결하지 못해서, 풀이를 검색해봤다. 접근이 달랐다. 주사위 자체를 어떻게 표현하여 규칙성 있게 움직이느냐를 고찰하기보다 회전을 했을때, 어떻게 변하느냐 만 생각하면 됐다. 서쪽으로 이동했을때 전개도면이 어떻게 변하는지 동쪽으로 이동했을때 전개도면이 어떻게 변하는지 북쪽으로 이동했을때 전개도면이 어떻게 변하는지 남쪽으로 이동했을때 전개도면이 어떻게 변하는지 이 '어떻게 변하는지'에 관점을 두면 풀 수 있었다. 그림을 그려주신 분이 계셔서, 해당 블로그를 올려놓는다. #include #include using namespace std; int N, M, K, sX, sY; int MAP[20][20]; // .. 2022. 7. 21.
[BaekJoon/백준] 9207번 페그 솔리테어 어떻게 풀지.. 하고 한시간 고민했다가 접근 방법을 찾아봤다. 간단하게 백트래킹으로 풀 수 있는 문제였다. 백트래킹이란, 내가 DFS의 활용에는 두 가지가 있다고 했었는데, 그 중 토글형 방식에 속한다. "선택해서 진행하고, 이전 상태로 되돌아오는 방식". stack 느낌으로 진행되는 방식이다. ( A = true; DFS(); A = false; 형식) 갈때까지 가며 DFS 해주면서, 토글을 통해 백트래킹(다시 되돌아가는)하고 또 진행하고..! /* 백트래킹(DFS 토글형) 문제였다. 갈때까지 가면서 진행해준다. */ #include #include #include using namespace std; int T; char MAP[5][9]; int mx[4] = {0, 0, -1, 1}; int my.. 2022. 7. 20.
반응형

티스토리툴바