2021-2022동계 모각코 / / 2022. 1. 6. 23:00

[동계 모각코 2차 회고]

동계 모각코 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 자체를 넣어주지 않는 알고리즘을 이용하여 해결하였다

https://tan-replace-29d.notion.site/92732505a55e463e959c57a7c8ac2de9?v=d5256e53ab6d41cfa86e67d246d8135f 

 

모각코

배성현의 모각코

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
  • 네이버 블로그 공유
  • 네이버 밴드 공유
  • 페이스북 공유
  • 카카오스토리 공유