글 읽기 - 엥..bfs로 풀었는데 맞았어요

lufovic77 7년 전 0

문제 보고 스타트 링크랑 숨바꼭질 문제 풀었던게 기억나서 bfs로 풀었는데 맞았네염

dp로 풀지 않고 이렇게 풀어도 제대로 푼거긴 한건가요?

#include <stdio.h>
int queue[2][10000000];
int visited[1000000];
int main(){
	int N;
	scanf("%d", &N);
	int current=N;
	int front=0,rear=0;
	visited[current]=-1;
	int count =0; 
	int i;
	queue[0][front]=current;
	queue[1][front]=count;
	while(current!=1){
		current=queue[0][front];
		count=queue[1][front];
		front++;		
		if(current%3==0 && visited[current/3]==0){
			rear++;
			queue[0][rear]=current/3;
			queue[1][rear]=count+1;
			visited[current/3]=-1;
		}
		if(current%2==0 && visited[current/2]==0){
			rear++;
			queue[0][rear]=current/2;
			queue[1][rear]=count+1;
			visited[current/2]=-1;
		}
		if(visited[current-1]==0&&current-1>=0){
			rear++;
			queue[0][rear]=current-1;
			queue[1][rear]=count+1;
			visited[current-1]=-1;
		}
	}
	printf("%d", count);
}

jseo 7년 전 0

네. 사실 모든 최적화 dp 문제는 acyclic 그래프에서 최단/최장거리 찾는 문제로 생각할수 있는데, 이 문제 같은 경우는 모든 간선 길이가 1이어서 bfs도 최적의 답을 냅니다.

lufovic77 7년 전 0

아 그렇군요.. 또 배워가네요 고맙습니다 ㅎ~~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

엥..bfs로 풀었는데 맞았어요

lufovic77 7년 전 0

jseo 7년 전 0

lufovic77 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말