Logo냥냠감자기술 블로그
Skip to Content
작성일: 2024-01-31

문제

백준 2636 - 치즈 

  • 난이도: 골드4
  • 알고리즘: DFS

코드

#include <iostream> #include <vector> using namespace std; const int dx[4]={1, 0, -1, 0}; const int dy[4]={0, -1, 0, 1}; int height, width; int cheeseNum(int y, int x, vector<vector<int> >& map, vector<vector<bool> >& visited) { if(x<0 || x>width-1 || y<0 || y>height-1) return 0; if(visited[y][x]) return 0; if(map[y][x]>0) { map[y][x]--; visited[y][x]=true; return 1; } visited[y][x]=true; int ret=0; for(int i=0; i<4; i++) { int nextY=y+dy[i], nextX=x+dx[i]; ret+=cheeseNum(nextY, nextX, map, visited); } return ret; } int getTime(vector<vector<int> >& map, int& lastCheeseSize) { int time=0; while(true) { vector<vector<bool> > visited(height, vector<bool>(width, false)); int currCheeseSize=cheeseNum(0, 0, map, visited); if(currCheeseSize==0) break; lastCheeseSize=currCheeseSize; time++; } return time; } int main() { cin>>height>>width; vector<vector<int> > map(height, vector<int>(width)); for(int i=0; i<height; i++) { for(int j=0; j<width; j++) { cin>>map[i][j]; } } int lastCheeseSize=0; cout<<getTime(map, lastCheeseSize)<<"\n"<<lastCheeseSize; }

회고

2638 문제 난이도 기여 하다가 2636 문제랑 똑같다고 해서 한번 풀어봤다. 난이도가 한단계 낮은 만큼 한 면만 치즈에 맞닿으면 녹기 때문에 풀기 더 쉬웠다. 이외에 2638문제와 크게 다르지 않았다.