leebaek

문제 (1, 1)칸에서 (N, M)칸까지 가는 최단 경로를 구하는 문제 -벽 하나를 부술 수 있음 생각 브루트포스로 풀면 N, M이 1000이하의 수여서 시간초과 뜸 아직 시간복잡도 계산할 줄 몰라서 그냥 풀어서 제출했더니, 시간초과가 아니라 런타임 레어가 떠서 당황함 힘들어서 구글링 해서 방법 찾았음 vis를 3차원 배열로 만들어서 벽을 부수었을 때와 부수지 않았을 때의 방문칸으로 나눠줌 문제풀이 1. 일단 bfs 문제랑 똑같음 2. 만약 해당 칸이 벽이라면, -1) 벽을 부순 적이 있는지 확인 -2) 없을 경우, 큐에 push 해줌 ( vis[][][1] / 0은 벽을 부수지 않았을 때, 1은 벽을 부수었을 때의 방문칸을 나타냄 / B+1 해줌 ) 3.만약 해당 칸이 벽이 아니라면 -1) 해당칸의 방..

문제 상자 안에 있는 토마토가 모두 익을 때까지의 최소 날짜를 구하는 문제 -익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 없는 칸은 -1로 표시됨 생각 7576번 토마토 문제의 업그레이드 문제임 3차원배열 사용해야겠구나 생각함 4칸은 원래 하던대로 탐색하면 될 것이고, 위, 아래를 어떤식으로 탐색하면 좋을지 생각했음 원래 BFS 풀던 코드에 반복문만 하나 추가해줬음 ( nz 확인 ) 문제풀이 1.vis배열을 -1로 초기화시킴 2. board에서 토마토가 들어있는 칸을 큐에 모두 집어넣음 -동시에 토마토가 익을 수 있음 2. 1번 과정에서 익지 않은 토마토 칸이 나오면 0 표시해줌 ( 나중에 토마토가 모두 익었는지 확인하기 위함 ) 익은 토마토가 나오면 1 표시 해줌 3. 반복문 사용해서 익은 토..

문제 정점과 간선의 개수가 주어지고, 연결요소의 개수를 구하는 문제 생각 전에 동아리할 때, 이런 문제 풀었었는데 기억이 안남 .. vector쓰면 간편하게 풀리는 문제였음!!!!!!!! -vector, size(), push_back() 개념 공부 필요.. 문제풀이 1.vector 배열을 만들어줌 -1 2를 입력받으면, graph[1] 컨테이너에 2값이 저장됨 -1 4를 입력받으면, graph[1] 컨테이너에 4값이 저장됨 -graph[1]에는 2와 4값이 저장되어있고, 사이즈는 2임 2.BFS 탐색 -pop된 i, graph[i].size() 탐색하는데, 방문하지 않을 경우에만 push해줌 3.연결된 요소 개수를 카운터 해주면 됨 코드 #include #include #include using nam..

문제 연구소에 벽 세개를 세워 확산되는 바이러스로부터 안전 영역의 최대 크기를 구하는 문제 바이러스는 벽을 통과할 수 없음 -빈칸은 0, 벽은 1, 바이러스는 2로 표시 생각 연구소에 벽 3개를 세워야 하는데, 세로, 가로 크기가 최대 8인걸 보고 브루트포스 문제라고 생각함 근데 구현을 못함. 그래서 구글링함 김재현이 이해도와줌 문제풀이 1. 벽 세개를 세우기 전에, 처음 입력받은 연구소 배열을 복사해둠 2.반복문 사용해서 벽 세개를 세움 -재귀 사용 -재귀의 베이스 조건이 cnt = 0 일 때, 벽 3개를 세운 배열을 BFS 탐색함 -백트래킹 (공부해야함) 3.BFS 돌려서 빈칸 개수 세고, 최댓값 구함 코드 #include #include #include using namespace std; #def..