동계 모각코 2차 종료 1.6 20:00 ~ 23:00
#개인별 회고
김동훈 -
백준 2644문제와 1068 문제를 파이썬으로 해결 하였다.
이번 회차는 dfs알고리즘을 공부하였고,
아직까지는 파이썬에 익숙하지 않았다. 자바에서 익숙하게 사용하던 자료구조들을 파이썬에서 어떻게 다룰지에 대한 고민이 문제 해결시간의 절반정도 차지하였다.
1068번 문제를 해결 할 때는 파이썬의 장점이 돋보였다. remove() 를 통해 리스트안의 값을 삭제시킬 수 있는 장점이 있었다.
https://kmentor.tistory.com/category/2021-2022%EB%8F%99%EA%B3%84%20%EB%AA%A8%EA%B0%81%EC%BD%94
'2021-2022동계 모각코' 카테고리의 글 목록
kmentor.tistory.com
배성현 -
1번 [https://www.acmicpc.net/problem/2644](https://www.acmicpc.net/problem/2644)
```jsx
var fs = require("fs");
var input = fs.readFileSync("/dev/stdin").toString().split("\n");
let C = parseInt(input[0]);
let start = parseInt(input[1].split(" ")[0]);
let end = parseInt(input[1].split(" ")[1]);
let m = parseInt(input[2]);
let list = [];
for (let i = 0; i <= C; i++) {
list[i] = [];
}
for (let i = 0; i < m; i++) {
let x = parseInt(input[3 + i].split(" ")[0]);
let y = parseInt(input[3 + i].split(" ")[1]);
list[x].push(y);
list[y].push(x);
}
function dfs(start, end, list) {
let st = [start];
let ans = [];
for (let i = 1; i <= C; i++) {
ans[i] = -1;
}
ans[start] = 0;
while (st.length != 0) {
let cur = st.pop();
for (let i = 0; i < list[cur].length; i++) {
let next = list[cur][i];
if (ans[next] === -1) {
ans[next] = ans[cur] + 1;
st.push(next);
}
}
}
return ans[end];
}
console.log(dfs(start, end, list));
```
기본적으로 이 문제는 dfs의 이동 횟수를 묻는 문제. 입력에서 시작점과 끝점을 주어졌으므로 ans배열에 자신을 제외한 정점을 -1로 초기화 한 후 자기자신을 0으로 두고 건너갈떄마다 자기자신의 +1 만큼 대입.
2번 [https://www.acmicpc.net/problem/1068](https://www.acmicpc.net/problem/1068)
```jsx
var fs = require("fs");
var input = fs.readFileSync("/dev/stdin").toString().split("\n");
let N = parseInt(input[0]);
let list = input[1].split(" ");
let deleteNode = parseInt(input[2]);
let child = [];
let root = -1;
for (let i = 0; i < N; i++) {
child[i] = [];
}
for (let i = 0; i < N; i++) {
let node = parseInt(list[i]);
if (node === -1) {
root = i;
continue;
}
if (i !== deleteNode) {
child[node].push(i);
}
}
function dfs(node, child) {
if (child[node].length === 0) {
return 1;
}
let ans = 0;
for (let i = 0; i < child[node].length; i++) {
ans += dfs(child[node][i], child);
}
return ans;
}
if (deleteNode === root) {
console.log(0);
} else {
console.log(dfs(root, child));
}
```
처음 풀이는 delete를 하지 않은 상태의 값에서 delete가 가진 값을 빼어 주었는데 예외가 발생하여서
delete를 할 node 자체를 넣어주지 않는 알고리즘을 이용하여 해결하였다
모각코
배성현의 모각코
tan-replace-29d.notion.site
임동윤 -
목표달성 현황
1. dfs알고리즘 학습 및 백준 문제 1개 풀기 (+골드문제) -> 목표달성
2. bfs알고리즘 문제 풀기 -> 목표달성
다짐.
지난주에 못 푼 문제들 포함하여 모두 풀게되었다. bfs, dfs문제는 정말정말 많으니 많이 풀어봐야겠다.
https://blog.naver.com/dyyim4725
잡동탱~ : 네이버 블로그
잡동사니 모인곳!
blog.naver.com
'2021-2022동계 모각코' 카테고리의 다른 글
[동계 모각코 3차 회고] (0) | 2022.01.13 |
---|---|
[동계 모각코 3차 목표] (0) | 2022.01.13 |
[동계모각코 2차 목표] (0) | 2022.01.06 |
[동계모각코 1차 회고] (0) | 2021.12.30 |
[동계모각코 1차 목표 ] (0) | 2021.12.30 |