그래프 탐색시 가로,세로 실수 - 백준 알고리즘 오답노트 1012

 

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

1012번: 유기농 배추

오류 복기

1. 가로와 연관된 변수 

즉, xy을 바꿔서 dfs돌렸음.. 

FB1.

가로 크기 = M
i = 0 ~ M까지 돌릴때
가로가 왔다 갔다 하는건 x 가 커졌다 작아졌다 하는 것.
graph [x][y]의 x 움직임

M - i - x ( 연관된 변수 적어두기)

int m;
int m_i;
int m_i_x;
이것도 하나의 방법

 

FB1. 다시 복기

 

1. 가로의 크기를 입력 받아 반복문을 돌릴 때 x관련 변수인데 y에 해당하는 변수로 생각함.

 

- 가로의 크기를 M으로 입력받음

- for i -> M까지 돌리면 

i변수는 가로의 크기만큼 반복되므로 2차원 좌표평면으로 볼 때 x의 좌표가 커진다고 볼 수 있다.

즉,

M - i - x 이렇게 연결돼 있다고 본다.

 

 

 

#2. 2차원 형태 graph 

 다음 노드로 갈 때 check list

1. 범위 벗어났는가?
2. graph[x][y] == 1 // 갈 수 있는 노드?
3. check[x][y] == false // 처음 방문 노드?

 

//1012
#include<cstdio>
#include<cstring>
int dx[4] ={0,0,1,-1};
int dy[4] ={1,-1,0,0};
using namespace std;
int graph[51][51];
bool check[51][51];
int m,n,k;
void dfs(int x,int y){
	check[x][y] = true;
	for( int i = 0; i < 4; i++){
		int nx = x + dx[i]; int ny = y + dy[i];
		//범위 체크
		if(nx >= 0 && nx < m && ny >= 0 && ny < n){
			if(graph[nx][ny] == 1 && check[nx][ny] == false){
				dfs(nx,ny);
			}			
		}
	}
}
int main(){
	int cases; scanf("%d",&cases);
	while(cases--){
		memset(graph,0,sizeof(graph));
		memset(check,0,sizeof(check));
		
// 가로길이 세로길이 배추가 심어진 곳 -> 1;
		scanf("%d %d %d",&m,&n,&k);
		for(int i = 0 ; i< k; i++){
			int x,y; scanf("%d %d",&x,&y);
			graph[x][y] = 1;
		}
		
		int result = 0;
		for(int i = 0; i<n; i++){
			for(int j =0 ; j<m; j++){
				if(graph[j][i] == 1 && check[j][i] == false){
					dfs(j,i); result++;
				}
			}
		}
		printf("%d\n",result);
	}
}
/*
FB1. 2차원 형태 graph
 다음 노드로 갈때 check list
1. 범위 벗어났는가?
2. graph[x][y] == 1	// 갈 수 있는 노드?
3. check[x][y] == false // 처음 방문 노드?
FB2. 가로와 연관된 변수 , 즉, xy을 바꿔서 dfs돌렸음..
가로 크기 = M
i = 0 ~ M까지 돌릴때
가로가 왔다 갔다 하는건 x 가 커졌다 작아졌다 하는것.
graph[x][y] 의 x 움직임
M - i - x ( 연관된 변수 적어두기)
int m;
int m_i;
int m_i_x;
이것도 하나의 방법
*/

 

 

 

 

 

플라즈마 IT 블로그 - 코딩 공부 정리, IT 정보 공유

 

https://plasmacodeing.tistory.com/