저도 어쩔 수 없는 노예라 좀 더 나은 노예 생활을 찾아 삼성 반도체 연구소의 지원했고, 총 두 차례에 걸쳐 삼성 SW 경력 인증 시험에 응시하였다.
평가 절차에 심각한 문제점이 있는 것은 아닌가 하는 의심이 많았지만, 결과적으로 떨어졌다.
하지만, 좀 더 나은 노예 생활을 향유하고자 하는 분들의 노고를 줄여 주고자.
기억에 의존해 두 차례의 삼성 SW 경력 인증 시험의 문제와 해답을 제공하고자 한다.
* 주의사항
기억에 의존해 문제와 해답을 유추한것으로 해당 포스트에 대한 정확성은 보장할 수 없으며,
전적으로 참조 만 할 것을 알려드립니다.
* 문제
N x N개의 파이프로 구성된 미로가 존재할때
각각의 파이프를 회전하여 1,1에서 n,n 까지 이동하는 최단 거리를 구하시요.
파이프의 종류
0: 파이프가 존재 하지 않음
1: '=' 모양의 파이프(좌쪽에서 우쪽으로 혹은 그 반대로 이동 가능)
2: '║' 모양의 파이프(위쪽에서 아래쪽으로 혹은 그 반대로 이동 가능)
3: '╚' 모양의 파이프(위쪽에서 우쪽으로 혹은 그 반대로 이동 가능)
4: '╔' 모양의 파이프(아래쪽에서 우쪽으로 혹은 그 반대로 이동 가능)
5: '╗' 모양의 파이프(아래쪽에서 왼쪽으로 혹은 그 반대로 이동 가능)
6: '╝' 모양의 파이프(좌쪽에서 위쪽으로 혹은 그 반대로 이동 가능)
시작 지점
1, 1 지점의 좌쪽이 시작
종료 지점
N, N 지점의 우쪽이 종료 지점
* 테스트 데이타
첫번째 라인은 NxN의 Array에 지정하는 N이 제공되고,
그 이후에 NxN에 해당하는 파이프의 종류가 제공된다.
예시)
더 나은 노예 생활을 향유하고자 하는 분들의 노고를 줄여 주고자.
기억에 의존해 두 차례의 삼성 SW 경력 인증 시험의 문제와 해답을 제공하고자 한다.
* 주의사항
기억에 의존해 문제와 해답을 유추한것으로 해당 포스트에 대한 정확성은 보장할 수 없으며,
전적으로 참조 만 할 것을 알려드립니다.
* 문제
N x N개의 파이프로 구성된 미로가 존재할때
각각의 파이프를 회전하여 1,1에서 n,n 까지 이동하는 최단 거리를 구하시요.
파이프의 종류
0: 파이프가 존재 하지 않음
1: '=' 모양의 파이프(좌쪽에서 우쪽으로 혹은 그 반대로 이동 가능)
2: '║' 모양의 파이프(위쪽에서 아래쪽으로 혹은 그 반대로 이동 가능)
3: '╚' 모양의 파이프(위쪽에서 우쪽으로 혹은 그 반대로 이동 가능)
4: '╔' 모양의 파이프(아래쪽에서 우쪽으로 혹은 그 반대로 이동 가능)
5: '╗' 모양의 파이프(아래쪽에서 왼쪽으로 혹은 그 반대로 이동 가능)
6: '╝' 모양의 파이프(좌쪽에서 위쪽으로 혹은 그 반대로 이동 가능)
10
1 1 1 1 1 1 5 0 0 0
0 0 0 0 0 0 2 0 0 0
0 4 1 1 1 1 6 5 0 0
0 2 0 0 0 0 0 2 0 0
4 3 1 1 5 1 1 6 5 0
2 0 0 4 6 0 4 1 6 0
3 1 5 3 1 1 1 5 0 0
0 0 2 0 0 0 4 6 0 0
0 0 3 5 0 0 2 0 3 5
0 0 0 3 1 1 3 1 6 3
주어진 NxN 파이프의 데이터의 시각화 된 결과
10
======╗
║
╔====╝╗
║ ║
╔╚==╗==╝╗
║ ╔╝ ╔=╝
╚=╗╚===╗
║ ╔╝
╚╗ ║ ╚╗
╚==╚=╝╚
* 해답
위에서 주어진 예시에 대한 최단 거리가 31이고 그 경로는 다음과 같다.
31
======╗
║
╚╗
║
╔==╝
╔╝
╚===╗
╔╝
║ ╔╗
╚=╝╚
* 소스코드
1: #include <stdio.h>
2:
3: #define INF (0x7fffffff)
4:
5: static int n;
6:
7: struct bin {
8: int pipe_type;
9: int inlet[4];
10: int outlet[4];
11: };
12:
13: static struct bin pipes[55][55];
14:
15: const int dx[4] = {0, 1, 0, -1};
16: const int dy[4] = {-1, 0, 1, 0};
17:
18: void DFS(int x, int y, int inlet_index)
19: {
20: struct bin &pipe = pipes[y][x];
21:
22: if (!(x >= 1 && x <= n && y >= 1 && y <= n)) return;
23:
24: if (pipe.pipe_type == 1 || pipe.pipe_type == 2) {
25: int outlet_index = (inlet_index + 2) % 4;
26: if (pipe.outlet[outlet_index] > pipe.inlet[inlet_index] + 1) {
27: pipe.outlet[outlet_index] = pipe.inlet[inlet_index] + 1;
28: struct bin &new_pipe = pipes[y+dy[outlet_index]][x+dx[outlet_index]];
29: int new_inlet_index = inlet_index;
30: if (new_pipe.inlet[new_inlet_index] > pipe.outlet[outlet_index]) {
31: new_pipe.inlet[new_inlet_index] = pipe.outlet[outlet_index];
32: DFS(x+dx[outlet_index], y+dy[outlet_index], new_inlet_index);
33: }
34: }
35: } else if (pipe.pipe_type == 3 || pipe.pipe_type == 4 ||
36: pipe.pipe_type == 5 || pipe.pipe_type == 6) {
37: int outlet_index = (inlet_index + 1) % 4;
38: if (pipe.outlet[outlet_index] > pipe.inlet[inlet_index] + 1) {
39: pipe.outlet[outlet_index] = pipe.inlet[inlet_index] + 1;
40: struct bin &new_pipe = pipes[y+dy[outlet_index]][x+dx[outlet_index]];
41: int new_inlet_index = (outlet_index + 2) % 4;
42: if (new_pipe.inlet[new_inlet_index] > pipe.outlet[outlet_index]) {
43: new_pipe.inlet[new_inlet_index] = pipe.outlet[outlet_index];
44: DFS(x+dx[outlet_index], y+dy[outlet_index], new_inlet_index);
45: }
46: }
47:
48: outlet_index = (inlet_index + 3) % 4;
49: if (pipe.outlet[outlet_index] > pipe.inlet[inlet_index] + 1) {
50: pipe.outlet[outlet_index] = pipe.inlet[inlet_index] + 1;
51: struct bin &new_pipe = pipes[y+dy[outlet_index]][x+dx[outlet_index]];
52: int new_inlet_index = (outlet_index + 2) % 4;
53: if (new_pipe.inlet[new_inlet_index] > pipe.outlet[outlet_index]) {
54: new_pipe.inlet[new_inlet_index] = pipe.outlet[outlet_index];
55: DFS(x+dx[outlet_index], y+dy[outlet_index], new_inlet_index);
56: }
57: }
58: }
59: }
60:
61: const char *pipe_shape[7] = {" ", "=", "║", "╚", "╔", "╗", "╝"};
62:
63: static int results[55][55] = {0, };
64:
65: int get_index_of_pipe(int inlet_index, int outlet_index)
66: {
67: if ((inlet_index == 3 && outlet_index == 1) ||
68: (inlet_index == 1 && outlet_index == 3)) return 1;
69: if ((inlet_index == 0 && outlet_index == 2) ||
70: (inlet_index == 2 && outlet_index == 0)) return 2;
71: if ((inlet_index == 0 && outlet_index == 1) ||
72: (inlet_index == 1 && outlet_index == 0)) return 3;
73: if ((inlet_index == 1 && outlet_index == 2) ||
74: (inlet_index == 2 && outlet_index == 1)) return 4;
75: if ((inlet_index == 2 && outlet_index == 3) ||
76: (inlet_index == 3 && outlet_index == 2)) return 5;
77: if ((inlet_index == 3 && outlet_index == 0) ||
78: (inlet_index == 0 && outlet_index == 3)) return 6;
79: return 0;
80: }
81:
82: void back_trace(int x, int y, int outlet_index)
83: {
84: struct bin &pipe = pipes[y][x];
85:
86: if (!(x >= 1 && x <= n && y >= 1 && y <= n)) return;
87:
88: if (pipe.pipe_type == 1 || pipe.pipe_type == 2) {
89: int inlet_index = (outlet_index + 2) % 4;
90: results[y][x] = get_index_of_pipe(inlet_index, outlet_index);
91: int prev_outlet_index = (inlet_index + 2) % 4;
92: back_trace(x+dx[inlet_index], y+dy[inlet_index], prev_outlet_index);
93: } else if (pipe.pipe_type == 3 || pipe.pipe_type == 4 ||
94: pipe.pipe_type == 5 || pipe.pipe_type == 6) {
95: int inlet_index = (outlet_index + 1) % 4;
96: if (pipe.inlet[inlet_index] == pipe.outlet[outlet_index] - 1) {
97: results[y][x] = get_index_of_pipe(inlet_index, outlet_index);
98: int prev_outlet_index = (inlet_index + 2) % 4;
99: back_trace(x+dx[inlet_index], y+dy[inlet_index], prev_outlet_index);
100: } else {
101: inlet_index = (outlet_index + 3) % 4;
102: if (pipe.inlet[inlet_index] == pipe.outlet[outlet_index] - 1) {
103: results[y][x] = get_index_of_pipe(inlet_index, outlet_index);
104: int prev_outlet_index = (inlet_index + 2) % 4;
105: back_trace(x+dx[inlet_index], y+dy[inlet_index], prev_outlet_index);
106: }
107: }
108: }
109: }
110:
111: int main(void)
112: {
113: FILE *fp = fopen("test.txt", "rt");
114:
115: fscanf(fp, "%d", &n);
116:
117: for (int i = 1; i <= n; ++i) {
118: for (int j = 1; j <= n; ++j) {
119: fscanf(fp, "%d", &pipes[i][j].pipe_type);
120: }
121: }
122:
123: fclose(fp);
124:
125: printf("%d\n", n);
126: for (int i = 1; i <= n; ++i) {
127: for (int j = 1; j <= n; ++j) {
128: printf("%s", pipe_shape[pipes[i][j].pipe_type]);
129: }
130: printf("\n");
131: }
132:
133: for (int i = 0; i <= n+1; ++i) {
134: for (int j = 0; j <= n+1; ++j) {
135: for (int k = 0; k < 4; ++k) {
136: pipes[i][j].inlet[k] = INF;
137: pipes[i][j].outlet[k] = INF;
138: }
139: }
140: }
141:
142: pipes[1][1].inlet[3] = 0;
143:
144: DFS(1, 1, 3);
145:
146: printf("%d\n", pipes[n][n].outlet[1]);
147:
148: back_trace(n, n, 1);
149:
150: for (int i = 1; i <= n; ++i) {
151: for (int j = 1; j <= n; ++j) {
152: printf("%s", pipe_shape[results[i][j]]);
153: }
154: printf("\n");
155: }
156: printf("end.\n");
157:
158: }
159:
