CS
[BaekJoon] 백준 2206번 벽 부수고 이동하기
[BaekJoon] 2206번 벽 부수고 이동하기 문제: https://www.acmicpc.net/problem/2206 내코드 - 정답률이 낮았던 이유가 있는 어려운 문제였다. - 우선, queue에는 좌표값, 거리, 벽을 부쉈는지 아닌지 여부를 넣어주었다. - 벽을 부수고 한 정점에 도착했느냐와 벽을 부수지 않고 도착했느냐가 다르기 때문에 visited배열에 벽을 부수고 왔는지/아닌지를 판별하기 위해 3차원으로 만들어주었다. - 그 다음으로 bfs안에서 다음 칸을 queue에 넣어줄지 말지 생각하는 조건이 4가지로 나뉘어진다. 1. 다음칸이 벽인데 이미 벽을 부순경우 -> 진행 불가. queue에 넣지 않고 지나간다. 2. 다음칸이 벽인데 벽을 아직 안부순경우 ->벽을 부쉈다는 표시를 해주고, qu..
[BaekJoon] 백준 7562번 나이트의 이동
[BaekJoon] 백준 7562번 나이트의 이동 문제: https://www.acmicpc.net/problem/7562 내코드 - 간단한 bfs문제 - queue를 초기화 시켜주는게 포인트 & 나이트의 이동방향을 dx, dy 로 선언해주기 - 아래는 아이패드에 정리한 내용 #include #include #include #include using namespace std; const int MAX = 301; int T = 0; int dx[] = { 1,2,2,1,-1,-2,-2,-1 }; int dy[] = { 2,1,-1,-2,-2,-1,1,2 }; int main(void) { ios::sync_with_stdio(false); cin.tie(0); cin >> T; while (T--) { ..
[BaekJoon] 백준 10026번 적록색약 - C++, Python
[BaekJoon] 백준 10026번 적록색약 문제: https://www.acmicpc.net/problem/10026 내코드 - 간단하게 bfs를 이용하는 문제 - 두 예제를 돌려야되서 초기화에 신경을 써줘야했다. - 아래는 아이패드에 정리한 내용 #include #include #include #include using namespace std; int n = 0; int arr[100][100] = { 0, }; int arr2[100][100] = { 0, }; queue qu; int res = 0; bool visited[100][100] = { false, }; pair cur; void isNear(int x, int y, int rgb[100][100]) { if (x < 0 || y ..
[BaekJoon] 백준 2583번 영역 구하기
[BaekJoon] 백준 2583번 영역 구하기 문제: https://www.acmicpc.net/problem/2583 내코드 - bfs문제 - 생각보다 정답률이 높은 문제였다. - 아래는 아이패드에 정리한 내용 #include #include #include #include #include using namespace std; int m, n, k; int arr[100][100]; bool visited[100][100] = { false, }; list li; queue qu; int cnt = 0; int isNear(int a, int b) { if (a = m || b >= n) return 0; if (arr[a][b] == 0 && visited[a][b..
[BaekJoon] 백준 1012번 유기농 배추(C++, Python)
[BaekJoon] 백준 1012번 유기농 배추 문제: https://www.acmicpc.net/problem/1012 내코드 - 기본적인 bfs문제 - 단지 테스트 케이스가 여러개 있어서 매번 초기화 해줘야한다는걸 주의해야했다. - 처음에 vector를 초기화를 안해줘서 계속 에러가 났다. - 다른 문제들에서는 인접 행렬(Adjacency Matrix)로 입력이 주어졌지만 여기선 인접 리스트(Adjacency List)로 쓰면 편한 형태로 주어졌다. 그래도 인접 행렬로 풀었다. - 아래는 아이패드에 정리한 내용. #include #include #include #include #include using namespace std; int T, m, n, k, cnt; int arr[50][50]; bo..
[BaekJoon] 백준 9466번 텀 프로젝트
[BaekJoon] 백준 9466번 텀 프로젝트 문제: https://www.acmicpc.net/problem/9466 내코드 - dfs문제인데 done배열을 추가해줘야하는 점이 조금 달랐다. - 정답률 24퍼센트의 약간 어려운 문제였다. - 아직도 완벽하게 이해는 가지 않는다 나중에 다시보기 - 사이클이 형성될 경우 사이클에 포함된 노드들의 수를 더하고 전체 학생수에서 빼면 됨. - (visited == true && done == false)이면 사이클이 있는것(이미 방문해서 visited == true이지만 사이클을 이룰 경우 재방문할 가능성이 있기 때문) - 따라서 현재 노드부터 다시 현재 노드로 돌아오기 전까지 cnt++을 해주면서 사이클 내에 있는 학생수를 세줌. - 순환 호출을 이용해서 품..
[BaekJoon] 백준 11724번 연결 요소의 개수
[BaekJoon] 백준 11724번 연결 요소의 개수 문제: https://www.acmicpc.net/problem/11724 내코드 - dfs를 이용해서 푸는 기본적인 그래프 문제 - 정점들을 차례대로 방문하면서 인접한 정점을 스택에 넣어준다. 이때 이미 방문했던 정점이면 패스. 패스하지 않은 정점의 개수가 연결요소의 개수. 이미 방문했던 정점이라는 것은 이전의 정점에서 dfs를 돌렸을때 연결되있어서 방문했다는 의미이니까. - 아래는 아이패드에 정리한 내용 코드블럭 #include #include #include #include using namespace std; int n, m; vector arr[1001]; bool visited[1001] = { false, }; int dfs() { st..
[Algorithm] 그래프(Graph)
[Algorithm] 그래프(Graph) 용어 그래프(Graph) : 정점(Node / Vertex)과 간선(Edge)으로 이루어진 자료구조 차수(degree) : 각 정점에 연결된 간선의 개수 루프(loop) : 한 정점에서 시작해 같은 정점으로 들어오는 간선 가중치 그래프(Weighted Graph) : 간선에 가중치가 표기된 그래프 무방향 그래프(Undirected Graph) : 그래프의 간선에 방향성이 없을 경우 방향 그래프(Directed Graph) : 그래프의 간선에 방향성이 있을 경우. 이때 자신에게서 나가는 간선을 outdegree, 들어오는 간선을 indegree라고 부름. 사이클(Cycle) : 임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로를 사이클이라고 부름. Cyc..