[BOJ] Puyo Puyo

[reasonyi]

문제 링크

https://www.acmicpc.net/problem/11559

풀이 사항

풀이 일자: 2024.00.00 풀이 시간: 00분 00초 채점 결과: 오답/시간 초과/런타임 에러/정답 예상 문제 유형: 구현/BFS/DFS/DP/자료구조/문자열 등 시간: 00 ms 메모리: 00 kb

풀이 방법

(풀이 접근 및 방법에 대한 설명 문제를 풀지 못했다면 어느 곳에서 어려움을 느꼈는지 적어주세요!!)

[reasonyi]

문제 링크

186

풀이 사항

풀이 일자: 2024.09.03 풀이 시간: 37분 21초 채점 결과: 정답 예상 문제 유형: 구현/BFS 시간: 104 ms 메모리: 14,180 kb

풀이 방법

• 맵의 아래에서부터 맵 전체를 탐색하며 아직 방문한 적 없는 블럭이 나오면 해당 블럭을 시작으로 bfs를 활용하여 같은 색상만 골라 사방탐색한다.
• 탐색이 끝난 후 방문한 블럭이 4개 이상이면 터트린다.
• down을 하기 전, 터트릴 수 있는 블럭이 더 있으면 다 터트린다.
• 다 터트린 후, down을 하고, 터트린 횟수를 +1한다.
• 위 과정을 터트릴 블럭이 없을 때까지 반복한다.

[sangholee235]

문제 링크

190

풀이 사항

풀이 일자: 2024.09.03 풀이 시간: 21분 23초 채점 결과: 정답 예상 문제 유형: BFS 구현 시간: 100 ms 메모리: 14,052 kb

풀이 방법

1. 만난적 없는 뿌요 만나면
2. 연결된 뿌요가 4개 이상인지 체크하고
3. 4개 이상이면 폭파 시키기
4. 폭파 한 뒤 맵 중력 업데이트
5. 몇 번 돌아갔는지 체크

[haesoooo]

문제 링크

194

풀이 사항

풀이 일자: 2024.09.04 풀이 시간: 45분 채점 결과: 정답 예상 문제 유형: DFS 시간: 108 ms 메모리: 14,252 kb

풀이 방법

while (true) {

1. 모든 cell을 돌면서 같은 색의 연결된 뿌요 개수 세기 : count() - 얘네 좌표를 다 저장한다. (coord 리스트에) 범위 내 && 방문 X && 다음 좌표 cell == 현재 좌표 cell 값) 개수 ++ 시키고, dfs 재귀
2. 뿌요 개수가 4개 이상일 때마다 걔네 터뜨리기 : bomb() - coord 리스트에 있던 애들 다 . 으로 변경시킨다
3. 이중 for문 내에서 현재 존재하는 뿌요 덩어리들을 다 터뜨린 후, 반복문 밖에서 애들을 내린다 - down() : 스택 이용
4. 1번의 연쇄가 끝났으므로 chaincnt++;

}

이중 for문을 돌렸을 때, 4개 이상의 뿌요 덩어리가 안나오면 while문을 종료시킴

[chanu2]

문제 링크

196

풀이 사항

풀이 일자: 2024.09.04 풀이 시간: 45분 채점 결과: 정답 예상 문제 유형: DFS 시간: 112 ms 메모리: 14308kb

풀이 방법

• 중력으로 떨어뜨리는 함수 구현
• 2중 for문을 통해서 bfs를 돌면서 4개 이상인 것들 확인
• 4개 이상인 좌표를 리스트에 넣고 for문 돌면서 터트리기
• 터지는게 없을 때 종료

[kimdevspace]

문제 링크

202

풀이 사항

• 풀이 일자 : 240905
• 풀이 시간 : 1시간
• 채점 결과 : 정답
• 예상 문제 유형 : BFS 구현
• 시간 : 104ms
• 메모리 : 14308kb

  풀이 방법

  한 싸이클에서

  1. 4칸 이상 뭉쳐있는 곳을 체크 해준다. < bfs
  2. 체크한 곳을 부셔준다. < bfs
  3. 블록을 내려준다. < 스택 자료구조 이용한 블록 내려주기 --- 4칸이상 뭉쳐있는 곳 없으면 break

[kro46]

문제 링크

206

풀이 사항

풀이 일자: 2024.09.05 풀이 시간: 3시간 32분 채점 결과: 정답 예상 문제 유형: 구현/BFS 시간: 108 ms 메모리: 14,540 kb

풀이 방법

여러 색상 그룹이 동시에 터질 수 있기 때문에 while(true)로 전체를 감싸서 하나의 색상이라도 폭발이 일어나면, 연쇄 폭발 수를 +1해주고 만약 하나도 터지지 않았다면 break; --> 이 부분 처리를 어떻게 하는지 몰라서 승규 형님의 도움을 받음(압도적 감사!) while문 안에서는 bfs로 같은 색상의 뿌요를 탐색하여 4개 이상이면 해당 위치를 '.'으로 변경하고 isPoped를 true로 반환, 모든 색상 검사가 끝나면 down() 을 수행한다. 만약 단 하나의 색상도 폭발이 일어나지 않으면 false를 반환하고 반복문을 탈출한다.

[kimjuheee]

문제 링크

208

풀이 사항

• 풀이 일자 : 240904
• 풀이 시간 : 4시간 25분
• 채점 결과 : 정답
• 예상 문제 유형 : 구현, DFS
• 시간 : 108 ms
• 메모리 : 14144KB

풀이 방법

• 같은 색 블록이 4개 이상 연결된 부분을 찾아 제거 반복
• 각 블록 그룹을 DFS로 탐색하여 크기를 확인하고, 크기 4 이상이면 해당 블록들을 제거
• 블록 제거 후, 빈 공간을 처리하기 위해 블록들이 아래로 떨어지도록 구현
• 제거, 낙하 끝나면 visit 초기화하고, 제거가 발생하면 다시 시뮬레이션을 반복
• 더 이상 제거할 블록이 없을 때까지 반복하며, 제거가 일어날 때마다 카운트를 증가시켜 결과 출력