https://www.acmicpc.net/problem/2178

풀이

• 빠른길은 BFS로 품
• 모든 가중치가 1이면 최단 거리 알고리즘은 BFS로 품
• BFS는 단계별로 진행됨. 즉 거리별로 진행됨. 거리가 1인곳가고, 거리가 2인곳 가고~

1. 입력값대로 미로 그림

2. 1,1 좌표를 큐에 넣음

3. 큐에서 pop

4. 점 이동

5. 이동한 점 큐에 넣음

6. 거리 계산

7. 3번으로

​

https://www.acmicpc.net/problem/11655

풀이

• 쉬운 문제
• 핵심 : 중간을 기준으로 +13, -13

1. a-n or A-N

+13

2. m-z or M-Z

-13

​

https://www.acmicpc.net/problem/4963

풀이

• 아파트 단지 문제랑 유사
• 그래프 문제이지만, 인접리스트 or 인접행렬 만들 필요 X
• 왜냐하면, 어떤 칸과 연결되어 있는 칸 : 상하좌우 네 칸 중에 있기때문에.
• 따러서, 모든 칸 마다 네 칸을 검사하면 됨

1. d[i][j]

   1 2	i,j 를 방문 X => d[i][j] = 0 i,j 를 방문 O => d[i][j] = 1

2. 방문을 아직 안했고, 아파트가 있으면

   1	dfs탐색으로 상하좌우 조사

​

https://www.acmicpc.net/problem/2667

풀이

• 연결요수 문제와 비슷
• 그래프 문제이지만, 인접리스트 or 인접행렬 만들 필요 X
• 왜냐하면, 어떤 칸과 연결되어 있는 칸 : 상하좌우 네 칸 중에 있기때문에.
• 따러서, 모든 칸 마다 네 칸을 검사하면 됨

1. d[i][j]

1
2

i,j 를 방문 X => d[i][j] = 0
i,j 를 방문 O => d[i][j] = 단지 번호

2. 방문을 아직 안했고, 아파트가 있으면

1

dfs탐색으로 상하좌우 조사

​

https://www.acmicpc.net/problem/9466

의문

• cycle 내의 개수를 셀 때 static 변수를 사용
• 왜 파라미터로 넘기면 계속해서 0으로 초기화 될까?

경우의 수

• 처음 방문
• 두 번째 방문, 같은 cycle
• 같은 cycle 내에서 이미 두 번을 방문
• 다른 cycle 내에서 이미 방문

https://www.acmicpc.net/problem/10451

풀이

• 이분그래프 풀이와 같음

2. check배열, 입력 배열 생성

3. 그래프 그림

4. dfs에 check배열과 입력 배열 넘김

5. 넘길때마다 ans++ (순열 사이클 찾는 방법)

6. dfs에서 재귀로 돌림

https://www.acmicpc.net/problem/1707

개념

1. 그래프를 다음과 같이 A와 B로 나눌 수 있으면 이분그래프

1

모든 간선의 한 끝은 A에, 다른 한 끝은 B에 있음.

2. DFS or BFS 로 풀 수 있음. check 배열이 포인트!!

1
2
3

check[i] == 0 : 아직 방문 X
check[i] == 1 : 방문 O, 빨간색
check[i] == 2 : 방문 O, 파란색

​

https://www.acmicpc.net/problem/11724

연결요소

1. 다음은 1개의 그래프가 2개의 연결 요소(Connected Component)로 이루어져 있는거임

   

2. DFS or BFS 로 풀 수 있음

   DFS나 BFS의 목적이 모든 정점을 한번 씩 방문하는 것이기 때문에

3. DFS 풀이

​

https://www.acmicpc.net/problem/2225

틀린 풀이

1. d[n][k]

1

k개 더해서 합이 n이 되는 경우의 수

2. d[n][k]

1

d[0][k-1] + d[1][k-1] + d[2][k-1] + ... + d[n][k-1]

맞는 풀이

​

https://www.acmicpc.net/problem/9461

틀린 풀이

1. p[i]를 나열해서 규칙을 찾음

2. p[i] = p[i-1] + p[i-5]

3. 결과 : 틀렸다고 나옴