congcoding

1. 문제 링크

www.acmicpc.net/problem/1260

2. 문제 설명

정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호, 간선이 연결하는 두 정점의 번호를 입력받아서

DFS를 수행한 결과와 BFS를 수행한 결과를 출력하는 문제입니다.

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 합니다.

3. 소스코드

BOJ 1260번 DFS와 BFS C++ 풀이입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

vector<int> e[1001];
bool check[1001];

void dfs(int v) {
	check[v] = true;
	cout << v << " ";
	for (int i = 0; i < e[v].size(); i++) {
		int next = e[v][i];
		if (!check[next])
			dfs(next);
	}
}

void bfs(int v) {
	queue<int> q;
	q.push(v);
	check[v] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << " ";
		for (int i = 0; i < e[cur].size(); i++) {
			int next = e[cur][i];
			if (!check[next]) {
				check[next] = true;
				q.push(next);
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, V, from, to;
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++) {
		cin >> from >> to;
		e[from].push_back(to);
		e[to].push_back(from);
	}

	for (int i = 1; i <= N; i++)
		sort(e[i].begin(), e[i].end());
	dfs(V);
	cout << '\n';
	memset(check, false, sizeof(check));
	bfs(V);

	return 0;
}

8번 라인 : 인접 리스트를 저장할 vector를 정점의 최대 개수가 1000이므로 e[1000]으로 접근할 수 있도록 1001의 크기로 선언했습니다.

9번 라인 : 정점의 방문을 체크할 배열 check도 마찬가지 이유로 1001의 크기로 선언했습니다.

45 ~ 49번 라인 : 입력으로 주어지는 간선은 양방향이므로 인접 리스트에 양방향으로 저장합니다.

51 ~ 52번 라인 : 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 하기 때문에 오름차순으로 정렬합니다.

53번 라인 : 탐색을 시작할 정점 V를 넘겨주면서 dfs 함수를 호출합니다.

11 ~ 19번 라인 : 재귀함수를 이용한 dfs입니다.

12번 라인 : 정점을 방문할 때 마다 check[v]를 true로 바꿔주면서 방문한 것을 표시하고,

13번 라인 : 해당 정점을 출력합니다.

14번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문을 돌면서,

15번 라인 : next변수에 현재 방문한 정점과 이어져 있는 정점을 저장하고,

16번 라인 : next정점을 방문한 적이 없으면(check[next] == false)

17번 라인 : next정점을 넘겨주면서 dfs 함수를 호출합니다.

55번 라인 : check 배열을 다시 false로 초기화하기 위해 memset함수를 이용합니다.

56번 라인 : 탐색을 시작할 정점 V를 넘겨주면서 bfs 함수를 호출합니다.

21 ~ 37번 라인 : queue를 이용한 bfs입니다.

23번 라인 : 처음 방문한 정점 v를 q에 push합니다.

25번 라인 : 처음 방문한 정점을 표시하기 위해 check[v]를 true로 바꿔줍니다.

25번 라인 : q가 비어있지 않는 동안

26번 라인 : cur변수에 현재 방문한 정점을 q.front()를 이용하여 저장하고,

27번 라인 : q.pop()을 이용하여 q에서 빼주고,

28번 라인 : 현재 방문한 정점을 출력합니다.

29번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문을 돌면서,

30번 라인 : next변수에 현재 방문한 정점과 이어져 있는 정점을 저장하고,

31번 라인 : next정점을 방문한 적이 없으면(check[next] == false)

32번 라인 : next정점을 방문하였다고 표시한 후(check[next] = true)

33번 라인 : q에 next정점을 push합니다.

1. List.generate란?

List<E>.generate(int length, E generator(int index),{bool growable: true})

length의 길이만큼 0부터 index - 1까지 범위의 각 인덱스를 오름차순으로 호출하여 만든 값으로 리스트를 생성합니다.

growable의 기본값은 true이고, false인 경우 생성된 리스트의 길이는 고정됩니다.

List<int>.generate(3, (int index) => index * index);

예를 들어 위와 같은 경우 length가 3이므로 0부터 2까지 오름차순으로 호출하면서 index * index의 값으로 리스트를 생성합니다.

따라서 결과는 [0, 1, 4]입니다.

2. 예제 결과

3. 예제 코드

import 'package:flutter/material.dart';

void main() => runApp(MyApp());

class MyApp extends StatelessWidget {
  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      title: 'Flutter Demo',
      theme: ThemeData(
        primarySwatch: Colors.yellow,
      ),
      home: MyHomePage(),
    );
  }
}

class MyHomePage extends StatelessWidget {
  final List<String> items = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '0', '#'];

  @override
  Widget build(BuildContext context) {
    return Scaffold(
      appBar: AppBar(
        title: Text('전화 자판 만들기'),
      ),
      body: GridView.count(
        crossAxisCount: 3,  // 열 개수
        children: List<Widget>.generate(items.length, (idx) {
          return Container(
            color: Colors.amber,
            padding: const EdgeInsets.all(40),
            margin: const EdgeInsets.all(8),
            child: Text(
                items[idx],
                style: TextStyle(fontSize: 40),
                textAlign: TextAlign.center,
            ),
          );
        }).toList()
      )
    );
  }
}

List.generate를 사용하지 않으면 body의 children에서 Container를 12번 써야 하지만,

Container를 List.generate를 통해 생성하고,

Text 값을 items에 미리 넣어놓고 해당 값을 idx로 가져오면 코드 길이를 1/12로 줄일 수 있습니다.

4. 참고한 사이트

1. DDL이란?

DDL은 Data Definition Language의 약자 데이터를 정의하는 언어로,

테이블 생성(CREATE), 생성된 테이블 구조의 변경(ALTER), 테이블 삭제(DROP)로 분류할 수 있습니다.

2. CREATE

• 테이블 생성

CREATE TABLE 테이블이름 (
    속성이름 데이터타입 [NOT NULL] [DEFAULT 기본값]
    [PRIMARY KEY (속성리스트)]
    [UNIQUE (속성리스트)]
    [FOREIGN KEY (속성리스트) REFERENCES 테이블이름(속성리스트)]
    [ON DELETE 옵션] [ON UPDATE 옵션]
    [CONSTRAINT 이름] [CHECK(조건)]
);

속성의 데이터 타입은 INT(정수), SMALLINT(INT보다 작은 정수), CHAR(n)(길이가 n인 고정 길이의 문자열), VARCHAR(n)(최대 길이가 n인 가변 길이의 문자열), NUMERIC(p, s)(고정 소수점 실수, p는 소수점을 제외한 전체 숫자의 길이고, s는 소수점 이하 숫자의 길이), FLOAT(n)(길이가 n인 부동 소수점 실수), REAL(부동 소수점 실수), DATE(연, 월, 일로 표현되는 날짜), TIME(시, 분, 초로 표현되는 시간), DATETIME(날짜와 시간) 등이 있습니다.

ON DELETE 옵션에는 NO ACTION(튜플을 삭제하지 못하게 함), CASCADE(관련 튜플을 함께 삭제함), SET NULL(관련 튜플의 외래키 값을 NULL로 변경함), SET DEFAULT(관련 튜플의 외래키 값을 미리 지정한 기본 값으로 변경함)이 있습니다.

ON UPDATE 옵션에는 NO ACTION(튜플을 변경하지 못하도록 함), CASCADE(관련 튜플에서 외래키 값을 함께 변경함), SET NULL(관련 튜플의 외래키 값을 NULL로 변경함), SET DEFAULT(관련 튜플의 외래키 값을 미리 지정한 기본 값으로 변경함)이 있습니다.

3. ALTER

• 새로운 속성의 추가

ALTER TABLE 테이블이름 ADD 속성이름 데이터타입 [NOT NULL] [DEFAULT 기본값];

• 기존 속성의 삭제

ALTER TABLE 테이블이름 DROP COULMN 속성이름;

• 새로운 제약조건의 추가

ALTER TABLE 테이블이름 ADD CONSTRAINT 제약조건이름 제약조건내용;

• 기존 제약조건의 삭제

ALTER TABLE 테이블이름 DROP CONSTRAINT 제약조건이름;

4. DROP

• 테이블의 삭제

DROP TABLE 테이블이름;