재귀 부분에서 dfs(nx,ny,cnt+1)을 

++cnt로 했는데 틀렸습니다 가 나왔다. 차이는 나중에 생각해 봐야겠다. 

새로 배운 것

1. 플러드 필에서 이동할 때 썼던 int dx,dy 배열을 한번에 2차원 배열로 사용하는 방법

2. 앞에것 을 방문했는지를 확인하는 데에 원래 배열을 만들어서 이전에 방문했던 지점을 

저장하고, for문을 이용해서 그 것을 매번 다음 nx,ny를 방문할 때마다 반복해야 했다. 

하지만 이 코드로 bool ch에 배열 number로 저장해서 한번에 찾을 수 있다는 걸 알았다. 

3. 백트래킹에 대해 아주 많이 생각해 보게 되었다. 



#include <iostream>
using namespace std;
int r, c;
char a[22][22];
bool ch[26];
int dd[][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
int ans = 0;
void dfs(int x, int y, int cnt) {
       if (cnt > ans) ans = cnt;
       for (int k = 0; k < 4; ++k) {
               int nx = x + dd[k][0];
               int ny = y + dd[k][1];
               if (0 <= nx&&nx < r && 0 <= ny&&ny < c) {
                      if (ch[a[nx][ny] - 'A'] == false) {
                              ch[a[nx][ny] - 'A'] = true;
                              dfs(nx, ny, cnt+1);
                              ch[a[nx][ny] - 'A'] = false;
                      }
               }
       }
}
int main() {
       cin >> r >> c;
       for (int i = 0; i < r; ++i) {
               cin >> a[i];
       }
       ch[a[0][0] - 'A'] = true;
       dfs(0, 0, 1);
       cout << ans;
       return 0;
       
}

저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 동전 2 2294  (0) 2018.04.02
[DP] 백준 2011 암호코드  (0) 2018.01.02
[그래프] 백준 5567 결혼식  (0) 2017.12.13
[EAZY] 백준 1065번 한수  (0) 2017.08.17
[EAZY] 백준 4673 셀프넘버  (0) 2017.08.15

boj.kr/5567

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.



풀이과정
첫번째 for : 양방향 그래프로 입력을 받는다. 
두번째 for : 1과 친구인 관계를 ch에 1로 저장하고 queue에 친구관계인 node를 push한다.
세번째 while : queue에 들어간 node를 하나씩 꺼내서 그 것과 연결된 노드 중 방문하지 않은 노드의 ch에 2를 저장한다.
마지막 for : ch가 1인 것과 2인 것의 개수를 센다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
queue<int> s;
vector<int> a[10001];
int ch[10001] = {0, };
int ans = 0;
int n;
int main() {
       cin >> n;
       int t;
       cin >> t;
       for (int i = 0; i < t; ++i) {
               int temp1, temp2;
               cin >> temp1 >> temp2;
               a[temp1].push_back(temp2);
               a[temp2].push_back(temp1);
       }
       int temlen = a[1].size();
       for (int i = 0; i < temlen; ++i) {
               ch[a[1][i]] = 1;
               s.push(a[1][i]);
       }
       while (!s.empty()) {
               int temp = s.front();
               s.pop();
               int len = a[temp].size();
               for (int j = 0; j<len; ++j)
                      if (ch[a[temp][j]] == 0) {
                              ch[a[temp][j]] = 2;
                      }
       }
       for (int i = 2; i <= n; ++i) {
               if (ch[i] == 2 || ch[i] == 1) {
                      ans++;
               }
       }
       cout << ans;
       return 0;
}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 2011 암호코드  (0) 2018.01.02
[그래프] 백준 1987 알파벳  (0) 2017.12.14
[EAZY] 백준 1065번 한수  (0) 2017.08.17
[EAZY] 백준 4673 셀프넘버  (0) 2017.08.15
백준 C++ 11721번  (0) 2017.08.15

+ Recent posts

티스토리툴바