본문 바로가기

백준 문제 풀이34

[백준 7562] 나이트의 이동 https://www.acmicpc.net/problem/7562 해설 일단, 그림만 봐도 BFS 라는 것을 짐작할 수있다. 색칠 된 부분의 좌표를 두 배열에 저장해놓고 BFS를 돌리면 풀 수있다. 현재 내 좌표를 0, 0으로 가정하고 나머지 색칠 된 부분의 좌표를 시계 방향으로 적어보겠다. int di[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int dj[8] = {1, 2, 2, 1, -1, -2, -2, -1}; 이 좌표를 가지고 현재 x와 y가 갈 수있는 좌표와 움직인 횟수를 큐에 넣어주고 업데이트 하면서 x와 y가 목적지에 도착하면 while을 빠져나와 count 한 값을 출력해주면 된다. ˙˙˙ 소스코드 #include #include using namespace std;.. 2020. 3. 20.
[백준 11403] 경로 찾기 https://www.acmicpc.net/problem/11403 해설 이번 문제도 11403번 플로이드 ( 참고 : https://far-simple.tistory.com/8 ) 문제와 마찬가지로 플로이드 와샬 알고리즘을 사용 해 푸는 문제입니다. 11403번 풀이에 플로이드에 관한 설명을 해놨으니 읽어보고 오시길 바라겠습니다. 문제에서 인접행렬이라고 써져있어서 뭐지? 싶을수도 있겠지만 그냥 N*N으로 출력하면 됩니다. 플로이드 점화식으로 중간에 임의의 점 k를 껴서 i->k 와 k-> j 에 길이 있다면 arr[i][j]를 1로 초기화 시켜주시면 됩니다. ˙˙˙ 소스 코드 #include using namespace std; int arr[101][101]; int main(){ int n; cin.. 2020. 3. 19.
[백준 11404] 플로이드 https://www.acmicpc.net/problem/11404 해설 문제의 제목을 보면 아시겠지만, 플로이드 와샬 알고리즘을 사용하는 문제입니다. 플로이드 와샬은 하나의 정점에서 출발해서 다른 정점으로부터의 최단 거리를 구하는 다익스트라 알고리즘과 달리 모든 정점에서 모든 정점으로의 최단 거리를 구할 때 사용됩니다. 플로이드 원리 플로이드의 원리라고 하면, 일단 1번, 2번, 3번 총 세개의 정점이 있다고 가정해봅시다. i) 1번에서 3번을 가는 데, 15원 ii) 1번에서 2번을 가는 데, 5원 iii) 2번에서 3번을 가는 데, 2원 여기서 우리는 1번 정점에서 3번 정점을 가기로 결정하고, 첫번째 만약 i번 방식으로 1번에서 바로 3번으로 간다면 15원이 들 것입니다. 하지만, 우리는 ii번 .. 2020. 3. 19.
[백준 11720] 숫자의 합 https://www.acmicpc.net/problem/11720 해설 숫자가 공백없이 주어지는 데 이 숫자들을 잘 떼어내면 되는 문제이다. 숫자들을 char 로 받아내고, char 값을 sum += (a[i]-'0'); 이렇게 코딩해준다면 char가 int 형 변수에 담기게 될 것이다. ˙˙˙ 소스코드 #include int main(){ char a[101]; int i,m,sum=0; scanf("%d",&m); scanf("%s", a); for(i=0; a[i]!='\0'; i++) { sum += (a[i]-'0'); } printf("%d",sum); } 2020. 3. 19.

티스토리툴바