틀린코드에요!
#include<stdio.h>
#include<stdlib.h>
int main()
{
int length, width;//세로, 가로
int x, y, direction;//방향은 0:북, 1:동, 2:남, 3:서
int** map;// 세로 가로, 0육지 1바다
scanf("%d %d", &length, &width);
map = (int**)malloc(sizeof(int*) * (length));
//int move[4][2] = {{0,-1}, {1,0}, {0,1}, {-1,0}};//북, 동, 남 ,서
int move[4][2] = { {0,-1}, {-1,0} ,{0,1} ,{1,0} };//북,서,남,동
scanf("%d %d %d ", &x, &y, &direction);
for (int i = 0; i < length; i++)
{
map[i] = (int*)malloc(sizeof(int) * width);
for (int j = 0; j < width; j++)
{
scanf("%d", &map[i][j]);
}
}
printf("firstmap\n");
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}
int count = 1;
int dire = 0; //북 서 남 동 순서
//int check = 1;
if (map[x][y] == 1)
count = 0;
while (1)
{
for (int k = 1; k <= 4; k++)
{
map[x][y] = 1;
if (direction == 0)//북쪽
dire = 0 + k;
else if (direction == 1)//동쪽
dire = 3 + k;
else if (direction == 2)//남쪽
dire = 2 + k;
else if (direction == 3)//서쪽
dire = 1 + k;
if (dire > 3)
dire -= 4;
printf("direction: %d\n", direction);
printf("move: %d %d", move[dire][0], move[dire][1]);
printf("--x:%d y:%d\n", x,y);
printf("serch it%d, %d: % d\n", x + move[dire][0], y + move[dire][1],map[x + move[dire][0]][y + move[dire][1]]);
if (0 <= x + move[dire][0] && x + move[dire][0] < length && 0 <= y + move[dire][1] && y + move[dire][1] < width)
{
if (map[x + move[dire][0]][y + move[dire][1]] == 0)
{
//check = 0;
count++;
printf("count: %d\n", count);
x += move[dire][0];
y += move[dire][1];
if (dire == 0)
direction = 0;
else if (dire == 1)
direction = 3;
else if (dire == 2)
direction = 2;
else if (dire == 3)
direction = 1;
break;
}
}
if (k == 4)
{
if (direction == 0)//북쪽
y += 1;
else if (direction == 1)//동쪽
x -= 1;
else if (direction == 2)//남쪽
y -= 1;
else if (direction == 3)//서쪽
x += 1;
}
printf("map\n");
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}
}
if (x < 0 || y < 0 || x >= width || y >= length)
{
//if (check)
// count = 0;
printf("%d", count);
return 0;
}
//printf("%d ,%d\n", x, y);
}
for (int i = 0; i < length; i++)
{
free(map[i]);
}
free(map);
}
여러번의 시행착오를 겪고 있다. 이취코테 게임개발 문제의 상위호완 문제라 쉽게 해결 할 수 있을줄 알았는데 생각보다 많이 헤매고 있다. x와 y값이 헷갈리기도 하고 방향 자체가 꺾이는 것도 헷갈려서 삽질을 참 많이 했다.. 이것도 맵을 만들어서 테스트를 해보니까 x와 y 값이 바껴서 탐색을 진행하고 있었다...다시 고쳐보자
이것도 틀린 코드에요!
#include<stdio.h>
#include<stdlib.h>
int main()
{
int length, width;//세로, 가로
int x, y, direction;//방향은 0:북, 1:동, 2:남, 3:서
int** map;// 세로 가로, 0육지 1바다
scanf("%d %d", &length, &width);
map = (int**)malloc(sizeof(int*) * (length));
//int move[4][2] = {{0,-1}, {1,0}, {0,1}, {-1,0}};//북, 동, 남 ,서
int move[4][2] = { {0,-1}, {-1,0} ,{0,1} ,{1,0} };//북,서,남,동
scanf("%d %d %d ", &x, &y, &direction);
for (int i = 0; i < length; i++)
{
map[i] = (int*)malloc(sizeof(int) * width);
for (int j = 0; j < width; j++)
{
scanf("%d", &map[i][j]);
}
}
printf("firstmap\n");
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}
int count = 1;
int dire = 0; //북 서 남 동 순서
//int check = 1;
if (map[y][x] == 1)
count = 0;
while (1)
{
for (int k = 1; k <= 4; k++)
{
map[y][x] = 2;
if (direction == 0)//북쪽
dire = 0 + k;
else if (direction == 1)//동쪽
dire = 3 + k;
else if (direction == 2)//남쪽
dire = 2 + k;
else if (direction == 3)//서쪽
dire = 1 + k;
if (dire > 3)
dire -= 4;
printf("direction: %d\n", direction);
printf("move: %d %d", move[dire][0], move[dire][1]);
printf("--x:%d y:%d\n", x,y);
//printf("serch it%d, %d: % d\n", x + move[dire][0], y + move[dire][1],map[y + move[dire][1]][x + move[dire][0]]);
if (0 <= y + move[dire][1] && y + move[dire][1] < length && 0 <= x + move[dire][0] && x + move[dire][0] < width)
{
if (map[y + move[dire][1]][x + move[dire][0]] == 0)
{
//check = 0;
printf("count: %d\n", count);
count++;
x += move[dire][0];
y += move[dire][1];
if (dire == 0)
direction = 0;
else if (dire == 1)
direction = 3;
else if (dire == 2)
direction = 2;
else if (dire == 3)
direction = 1;
break;
}
}
if (k == 4)
{
if (direction == 0)//북쪽
y += 1;
else if (direction == 1)//동쪽
x -= 1;
else if (direction == 2)//남쪽
y -= 1;
else if (direction == 3)//서쪽
x += 1;
}
}
printf("map\n");
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
printf("%d ", map[i][j]);
}
printf("\n");
}
if (x < 0 || y < 0 || x >= width || y >= length)
{
//if (check)
// count = 0;
printf("%d", count);
return 0;
}
//printf("%d ,%d\n", x, y);
}
for (int i = 0; i < length; i++)
{
free(map[i]);
}
free(map);
}나름대로 깔끔하게 고쳤다고 생각하고 문제도 없다고 생각되는데 뭐가 문제인지 모르겠다... 원하는대로 구현을 했는데 문제에서 원하는 구현이 이게 아닌가보다.
어떤분이 정리 해놓으신 사진을 봤는데 나랑 x축과 y축이 다르다... 아니 이걸 고쳤는데 다시 고쳐야되네,,,
이것도 틀린 코드에요!
#include<stdio.h>
#include<stdlib.h>
int main()
{
int length, width;//세로, 가로
int x, y, direction;//방향은 0:북, 1:동, 2:남, 3:서
int** map;// 세로 가로, 0육지 1바다
scanf("%d %d", &length, &width);
map = (int**)malloc(sizeof(int*) * (length));
//int move[4][2] = {{0,-1}, {1,0}, {0,1}, {-1,0}};//북, 동, 남 ,서
int move[4][2] = { {0,-1}, {-1,0} ,{0,1} ,{1,0} };//북,서,남,동
scanf("%d %d %d ", &y, &x, &direction);
for (int i = 0; i < length; i++)
{
map[i] = (int*)malloc(sizeof(int) * width);
for (int j = 0; j < width; j++)
{
scanf("%d", &map[i][j]);
}
}
/*printf("firstmap\n");
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}*/
int count = 1;
int dire = 0; //북 서 남 동 순서
//int check = 1;
if (map[y][x] == 1)
count = 0;
while (1)
{
for (int k = 1; k <= 4; k++)
{
map[y][x] = 2;
if (direction == 0)//북쪽
dire = 0 + k;
else if (direction == 1)//동쪽
dire = 3 + k;
else if (direction == 2)//남쪽
dire = 2 + k;
else if (direction == 3)//서쪽
dire = 1 + k;
if (dire > 3)
dire -= 4;
//printf("direction: %d\n", direction);
//printf("move: %d %d", move[dire][0], move[dire][1]);
//printf("--x:%d y:%d\n", x,y);
//printf("serch it%d, %d: % d\n", x + move[dire][0], y + move[dire][1],map[y + move[dire][1]][x + move[dire][0]]);
if (0 <= y + move[dire][1] && y + move[dire][1] < length && 0 <= x + move[dire][0] && x + move[dire][0] < width)
{
if (map[y + move[dire][1]][x + move[dire][0]] == 0)
{
//check = 0;
//printf("count: %d\n", count);
count++;
x += move[dire][0];
y += move[dire][1];
if (dire == 0)
direction = 0;
else if (dire == 1)
direction = 3;
else if (dire == 2)
direction = 2;
else if (dire == 3)
direction = 1;
break;
}
}
if (k == 4)
{
if (direction == 0)//북쪽
y += 1;
else if (direction == 1)//동쪽
x -= 1;
else if (direction == 2)//남쪽
y -= 1;
else if (direction == 3)//서쪽
x += 1;
}
}
/*printf("map\n");
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
printf("%d ", map[i][j]);
}
printf("\n");
}*/
if (x < 0 || y < 0 || x >= width || y >= length)
{
//if (check)
// count = 0;
printf("%d", count);
return 0;
}
//printf("%d ,%d\n", x, y);
}
for (int i = 0; i < length; i++)
{
free(map[i]);
}
free(map);
}수정해서 완성했다고 생각했는데 이것도 틀렸다고 나온다... 그래서 여러개의 반례들을 돌려봤는데
7 7
4 2 1
1 1 1 1 1 1 1
1 0 0 0 1 0 1
1 0 1 1 0 0 1
1 0 0 0 0 1 1
1 0 0 1 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
>>15
가 나왔다 정답은 11이어야한다고 하는데 왜지,,,,
맞다 그림을 그려보니까 11을 나오는게 맞다 과연 어디서 에러가 나는지 다시 디버깅을 해봐야겠다.
찾았다. 나는 만약 뒤로가서 사방이 막혀있으면 한번 더 뒤로 갔다. 어라 근데 문제 조건대로라면 뒤로 가는게 맞지 않나...?
아 나는 문제를 또 잘못 읽었다. 벽이 있었다. 원래 주어진 1은 벽이고 내가 2로 만든것만 뒤로 갈 수 있었던 것이다...
이제는 정답코드!!
#include<stdio.h>
#include<stdlib.h>
int main()
{
int length, width;//세로, 가로
int x, y, direction;//방향은 0:북, 1:동, 2:남, 3:서
int** map;// 세로 가로, 0육지 1바다
scanf("%d %d", &length, &width);
map = (int**)malloc(sizeof(int*) * (length));
//int move[4][2] = {{0,-1}, {1,0}, {0,1}, {-1,0}};//북, 동, 남 ,서
int move[4][2] = { {0,-1}, {-1,0} ,{0,1} ,{1,0} };//북,서,남,동
scanf("%d %d %d ", &y, &x, &direction);
for (int i = 0; i < length; i++)
{
map[i] = (int*)malloc(sizeof(int) * width);
for (int j = 0; j < width; j++)
{
scanf("%d", &map[i][j]);
}
}
/*printf("firstmap\n");
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}*/
int count = 1;
int dire = 0; //북 서 남 동 순서
//int check = 1;
if (map[y][x] == 1)
count = 0;
while (1)
{
for (int k = 1; k <= 4; k++)
{
map[y][x] = 2;
if (direction == 0)//북쪽
dire = 0 + k;
else if (direction == 1)//동쪽
dire = 3 + k;
else if (direction == 2)//남쪽
dire = 2 + k;
else if (direction == 3)//서쪽
dire = 1 + k;
if (dire > 3)
dire -= 4;
//printf("direction: %d\n", direction);
//printf("move: %d %d", move[dire][0], move[dire][1]);
//printf("--x:%d y:%d\n", x,y);
//printf("serch it%d, %d: % d\n", x + move[dire][0], y + move[dire][1],map[y + move[dire][1]][x + move[dire][0]]);
if (0 <= y + move[dire][1] && y + move[dire][1] < length && 0 <= x + move[dire][0] && x + move[dire][0] < width)
{
if (map[y + move[dire][1]][x + move[dire][0]] == 0)
{
//check = 0;
//printf("count: %d\n", count);
count++;
x += move[dire][0];
y += move[dire][1];
if (dire == 0)
direction = 0;
else if (dire == 1)
direction = 3;
else if (dire == 2)
direction = 2;
else if (dire == 3)
direction = 1;
break;
}
}
if (k == 4)
{
if (direction == 0)//북쪽
y += 1;
else if (direction == 1)//동쪽
x -= 1;
else if (direction == 2)//남쪽
y -= 1;
else if (direction == 3)//서쪽
x += 1;
//check++;//한칸 뒤로 갔음을 표시
}
}
/*printf("map\n");
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
printf("%d ", map[i][j]);
}
printf("\n");
}*/
if (map[y][x]==1|| x < 0 || y < 0 || x >= width || y >= length)
{
//if (check)
// count = 0;
printf("%d", count);
return 0;
}
//printf("%d ,%d\n", x, y);
}
for (int i = 0; i < length; i++)
{
free(map[i]);
}
free(map);
}결국 정답코드는 위와 같다.
중요한 조건은
1. 탐색하는 방향과 현재 방향의 차이를 이용해서 문제에 적용하기.
2. 문제에서 아에 뒤로 돌아갈수 없는 곳으로 돌아가지 않는 것이다.
3. 그리고 문제 조건에서 x와 y의 위치를 착각하지 않는것
이 세가지만 헷갈리지 않는다면 문제푸는 시간을 많이 단축 할 수 있었을 것 같다.
삼성 코딩테스트로 나온 문제라고 하는데 시간은 오래걸렸지만 내 힘으로 풀었다는 게 매우 뿌듯했다.
이 글은 코딩 꼬꼬마 시절에 푼 문제를 보관한 글로 네이버에 저장해둔 글을 옮긴 글입니다.
혹시나 참고하시는 부분에 이상한 부분이나 질문이 생긴다면 남겨주시면 친절히 답변 드리겠습니다.
728x90
'초기 네이버 기록 > 알고리즘(C)' 카테고리의 다른 글
| 백준 (C언어)그리디 알고리즘 단어수학 백준1339번 (0) | 2023.01.04 |
|---|---|
| 백준 (C언어)백준 1331번 구현 알고리즘 시뮬레이션(나이트) (0) | 2023.01.04 |
| 백준 (C언어)백준 10828번 스택 스택 구현문제 (0) | 2023.01.04 |
| 백준 (C언어)백준 DFS와 BFS문제 1260번 (0) | 2023.01.04 |
| 백준 (C언어)백준2667번 단지번호 붙히기 (0) | 2023.01.04 |